Python 이진 탐색(Binary Search) 완벽 가이드: 원리부터 구현까지

이진 탐색(Binary Search)은 정렬된 배열에서 특정 원소를 찾는 데 사용되는 탐색 알고리즘입니다. 정렬되지 않은 배열에는 사용할 수 없다는 점에 유의해야 합니다. 이진 탐색은 시간 복잡도 측면에서 선형 탐색(Linear Search)보다 훨씬 효율적인 알고리즘으로 널리 알려져 있습니다.

선형 탐색의 시간 복잡도는 O(n)인 반면, 이진 탐색의 시간 복잡도는 O(log n)입니다. 따라서 이진 탐색은 더 빠르고 효율적인 탐색 방법이지만, 반드시 정렬된 배열에서만 사용할 수 있다는 제약 조건이 있습니다.

이진 탐색의 작동 원리

이진 탐색의 핵심 아이디어는 찾으려는 원소를 배열의 모든 요소와 일일이 비교하는 대신, 배열의 중앙에 있는 원소와 비교하는 것입니다.

비교 결과가 다음과 같이 진행됩니다.

중앙 원소가 찾는 값이라면 → 탐색 성공, 종료
찾는 값이 중앙 원소보다 작다면 → 배열이 정렬되어 있으므로 해당 값은 반드시 왼쪽(앞쪽) 절반에 존재
찾는 값이 중앙 원소보다 크다면 → 해당 값은 반드시 오른쪽(뒤쪽) 절반에 존재

이처럼 이진 탐색은 매 단계마다 탐색 범위를 절반으로 줄여 나갑니다. 선택된 절반 범위에 대해 위 과정을 재귀적으로(또는 반복적으로) 적용하여 원하는 원소를 찾을 때까지 진행합니다.

인덱스 기반 탐색 과정

구체적으로 탐색은 다음과 같이 진행됩니다.

왼쪽 인덱스(L)를 0으로, 오른쪽 인덱스(H)를 배열의 마지막 인덱스로 설정합니다.
중앙 인덱스(mid)를 계산합니다. mid = (L + H) / 2
찾는 값이 중앙 원소보다 작으면 오른쪽 인덱스를 H = mid - 1로 변경하여 앞쪽 절반만 살펴봅니다.
찾는 값이 중앙 원소보다 크면 왼쪽 인덱스를 L = mid + 1로 변경하여 뒤쪽 절반만 살펴봅니다.
선택된 절반 범위에 대해 위 과정을 반복합니다.

원소가 배열에 없는 경우 어떻게 판단할까?

탐색을 멈추고 '원소가 배열에 존재하지 않음'을 판단할 수 있는 종료 조건이 필요합니다. 왼쪽 인덱스(L)가 오른쪽 인덱스(H)보다 작거나 같은 동안만 반복해서 탐색을 진행하며, 이 조건이 거짓이 되었는데도 원소를 찾지 못했다면 그 원소는 배열에 존재하지 않는 것입니다.

예제로 이해하기

다음과 같은 정렬된 배열에서 원소 6을 찾는다고 가정해 보겠습니다.

1단계: L=0, H=8, Mid=4

중앙값 10과 비교했을 때 6 < 10이므로, 찾는 값은 앞쪽 절반에 있습니다.
H = Mid - 1 적용

2단계: L=0, H=3, Mid=1

중앙값 5와 비교했을 때 6 > 5이므로, 찾는 값은 뒤쪽 절반에 있습니다.
L = Mid + 1 적용

3단계: L=2, H=3, Mid=2

6 == 6, 원소를 찾았습니다!

따라서 원소 6은 인덱스 2에 위치함을 확인할 수 있습니다. 단 세 번의 비교만으로 원소를 찾아낸 것이죠.

Python 코드 구현

주어진 정렬된 배열에서 원하는 원소를 탐색하고, 원소가 존재하면 해당 인덱스를 출력하고, 존재하지 않으면 -1을 출력하는 프로그램을 만들어 보겠습니다.

예제 코드

def binary_search(arr, x):
    l = 0
    r = len(arr) - 1
    while(l <= r):
        mid = (l + r) // 2
        if(arr[mid] == x):
            return mid
        elif(x < arr[mid]):
            r = mid - 1
        elif(x > arr[mid]):
            l = mid + 1
    return -1

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
a = 7
print(binary_search(array, a))
b = 15
print(binary_search(array, b))

실행 결과

6
-1

결과 해석:

원소 7은 배열의 인덱스 6에 존재하므로 6이 출력됩니다.
원소 15는 배열에 존재하지 않으므로 -1이 출력됩니다.

마무리

이진 탐색은 데이터 양이 많아질수록 그 효율성이 더욱 두드러집니다. 예를 들어 100만 개의 원소가 있는 배열에서도 최대 약 20번의 비교만으로 원소를 찾을 수 있습니다. 다만 사용 전에 반드시 배열이 정렬되어 있어야 한다는 전제 조건을 기억하세요. 정렬되지 않은 데이터라면 먼저 정렬을 수행한 후 이진 탐색을 적용하는 것이 좋습니다.