[Algorithm] 이분 탐색 (Binary Search)

 

 

 

 

이진 탐색

검색 간격을 반으로 반복적으로 나누어 정렬된 배열로 사용하는 알고리즘

• 대상 요소와 검색 공간의 중간 값을 비교하여 검색 간격을 절반으로 줄임.

 

 

✍🏻  동작 예시

index

0

1

2

3

4

5

6

7

8

9

 

-5

-2

0

1

2

4

5

6

7

10

Low

Middle

High

---

-5

-2

0

1

2

4

5

6

7

10

Low

Middle

High

---

-5

-2

0

1

2

4

5

6

7

10

Low Middle

High

 

 

 

이진 검색 알고리즘 적용 조건

• 데이터 구조를 정렬
• 데이터 구조의 모든 요소에 액세스하려면 일정 시간 소요

 

 

 

작동 방식

1. 배열의 중간 요소를 Key와 비교한다. (Key는 찾고자 하는 요소)
   • 키를 찾으면 프로세스 종료
2. 키를 찾지 못한 경우 다음 공간으로 탐색할 배열의 절반을 선택한다.
   • 키가 중간 요소보다 작으면  →   중간을 기준으로 왼쪽 사용
   • 키가 중간 요소보다 크면     →   중간을 기준으로 오른쪽 사용

 

 

 

예시

배열 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], key = 23

 

 

index

0

1

2

3

4

5

6

7

8

9

 

2

5

8

12

16

23

38

56

72

91

Low = 0

Mid = 4

High = 9

---

2

5

8

12

16

23

38

56

72

91

Low = 5

Mid = 7

High = 9

---

2

5

8

12

16

23

38

56

72

91

Low = 5 Mid = 5

High = 6

 

 

 

재귀 Code

def binary_search(arr, target, low, high):
    if low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binary_search(arr, target, low, mid - 1)
        else:
            return binary_search(arr, target, mid + 1, high)
    else:
        return -1

 

 

 

반복문 Code

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    return -1