Skip to main content
동호의 블로그

이분 탐색 알고리즘 [개념]

•1 min•149 words

https://gliver.tistory.com/31

1. 이분 탐색 알고리즘

  • 이분 탐색(Binary Search) 알고리즘은 정렬된 배열에서 특정한 원소를 찾는 알고리즘이다.
    • 정렬된 배열이 아니라면, 이분 탐색 알고리즘은 사용할 수 없다.

2. 선형 탐색 vs 이분 탐색

  • 선형 탐색
    • 특정한 원소를 선형 탐색으로 찾는다면, O(N)O(N)의 시간 복잡도가 걸린다.
    • 정렬이 되어 있지 않은 상태에서도 사용 가능하다.
  • 이분 탐색
    • 특정한 원소를 이분 탐색으로 찾는다면, O(logN)O(logN)의 시간 복잡도가 걸린다.
    • 정렬이 된 상태에서만 사용 가능하다.

3. 이분 탐색 알고리즘 구현

**방법1** - $O(logN)$

  • left와 right 변수를 통해서, 원소의 범위를 좁혀나가는 방식이다.

    image.png

    • 종료 조건: left > right
**예제 코드** 
def binary_search(arr, num): # arr[idx] = num인 idx를 반환
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2

        if arr[mid] < num: 
            left = mid + 1

        if arr[mid] > num: 
            right = mid - 1
            
        if arr[mid] == num: 
            return mid

    return -1

arr = [1, 2, 4, 5, 7, 9, 10, 12, 14]
print(binary_search(arr, 10))
**방법2** - $O(logN)$

  • 현재 위치 cur과 탐색할 보폭 step을 이용해서, 원소를 찾아가는 방식이다.

    image.png

    • 종료 조건: step == 0
**예제 코드** 
def binary_search(arr, num): # arr[idx] ≤ num인 가장 큰 idx를 반환
    cur = -1
    step = len(arr)
    
    while step != 0:
        while (cur + step < len(arr) and arr[cur + step] <= num): 
            cur += step
        step //= 2
        
    return cur

arr = [1, 3, 3, 4, 5, 7, 9, 10, 11, 13, 13, 16]
print(binary_search(arr, 10))

4. 실제 문제에서 이분 탐색 알고리즘

  • 이분 탐색 알고리즘은 정렬이 된 상태에서만 사용할 수 있다.
  • 따라서, 정렬이 가능한 상황(또는 정렬이 되어 있는 상태)이라면 이분 탐색을 고려하면 된다.