이진 탐색(Binary Search) 의 개념

이진 탐색은 분할정복 방법을 이용해 배열 형태로 주어진 데이터에서 원하는 값을 가진 데이터를 찾는 것입니다. 이진 탐색은 탐색의 대상이 되는 데이터가 정렬된 상태라면 효과적으로 탐색을 수행할 수 있습니다. 이진 탐색은 탐색 키를 아래의 과정을 통해서 찾습니다.

• 분할: 배열을 가운데 원소를 기준으로 왼쪽 부분배열과 오른쪽 부분배열로 분할합니다. 탐색키가 가운데 원소와 같다면 가운데 원소에 대항다는 배열의 인덱스를 반환하고 종료합니다.
• 정복: 탐색키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출합니다.
• 결합: 부분배열에 대해서 이진 탐색의 결과가 직접 반환되므로 결과를 결합할 필요는 없습니다.

이진 탐색의 Python 구현

Python 으로 이진 탐색을 아래와 같이 구현할 수 있습니다.

def binary_search(arr: list, x: int) -> int:
    l, r = 0, len(arr) - 1

    while l <= r:
        mid = l + (r - l) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            l = mid + 1
        else:
            r = mid - 1

    return -1

위에서 설명한 순서를 그대로 작성하면 됩니다. 가운데부터 시작하여 가운데 원소가 찾는 값과 같으면 그 값의 인덱스를 반환하고, 그렇지 않으면 값의 대소에 따라 오른쪽과 왼쪽을 탐색합니다.

이진 탐색의 성능 분석과 특징

• 이진 탐색의 시간 복잡도를 T(n), 입력 크기를 n 이라고 한다면, T(n) 은 탐색 과정에서 수행되는 모든 비교 횟수의 합으로 표현할 수 있습니다. T(n)=T(n/2)+1, T(1)=1 과 같은 점화식에 의해 계산될 수 있는데, 이진 탐색의 시간 복잡도는 O(logn) 입니다.
• 이진 탐색은 입력이 정렬된 리스트일 때에만 적용이 가능합니다.
• 데이터의 삽입, 삭제 연산을 수행하면 데이터의 이동이 발생합니다.
• 고로, 이진 탐색은 데이터의 삽입과 삭제가 빈번한 응용에서의 탐색으로는 적합하지 않습니다.