이분 탐색(이진 탐색, binary search)

게시 2024/02/17

By 신건우 5 분읽는 시간

이분 탐색, 이진 탐색, Binary Search

이분 탐색(이진 탐색)은 결정 문제(Decision Problem)의 답이 이분적(T or F)일 때 사용할 수 있는 탐색 기법이다. 보통 1개의 parameter에 대해 탐색할 때사용한다.

이분 탐색을 사용하면 정렬된 배열에서 특정 값을 효율적으로 찾을 수 있다.

길이가 $N$인 배열에 대한 완전 탐색은 $O(N)$ 의 시간 복잡도를 가지지만, 이분 탐색을 이용하여 해당 배열을 탐색하는 경우는 $O(\log N)$이다.

아이디어

정렬된 배열의 가장 왼쪽 인덱스(left)와 가장 오른쪽 인덱스(right)를 가지고, 중간의 값(mid)을 계산한다.
계산된 mid를 우리가 찾고자하는 target 값과 비교한다.
1. 중간 값이 타겟 값과 동일하다면, 해당 중간 값을 반환
2. 중간 값 < 타겟 값이라면, left를 중간 값 다음 인덱스로 업데이트 후 1~2를 반복
3. 중간 값 > 타겟 값이라면, right을 중간 값 이전 인덱스로 업데이트 후 1~2를 반복

반복하여 타겟값을 찾거나, left와 right가 교차할 때(left>right)까지 반복한다.

분할 정복과의 차이점

분할 정복의 경우 전체 문제에 대해 분할하여 가장 작은 형태로 만드는 것에 반해,

이분 탐색은 정답이 포함되지 않은 부분은 추가로 탐색하지 않는다.

구현

1. 재귀

  
def binary_search(arr, target, left, right):
    if left > right:
        return -1  # 탐색 실패

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    else:
        return binary_search(arr, target, left, mid - 1)

# 예시 사용
arr = [1, 3, 5, 7, 9, 11]
target = 7

result = binary_search(arr, target, 0, len(arr) - 1)

if result != -1:
    print("타겟이 배열의 인덱스", result, "에 위치합니다.")
else:
    print("타겟을 찾을 수 없습니다.")

2. 반복문

  
def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # 탐색 실패

# 예시 사용
arr = [1, 3, 5, 7, 9, 11]
target = 7

result = binary_search(arr, target)

if result != -1:
    print("타겟이 배열의 인덱스", result, "에 위치합니다.")
else:
    print("타겟을 찾을 수 없습니다.")

유의 사항

이분 탐색은 off-by-one error가 발생하기 쉬우므로,

반복문의 구간 설정 또는 left, right 변수를 업데이트 할 때 유의해야한다.

반복문에서 루프가 한번 더 실행되거나 덜 실행되는 경우의 오류
일반적으로 인덱스를 잘못 처리하거나, 반복문의 범위를 잘못 설정하여 발생한다. 예를 들어, 배열의 인덱스를 0부터 시작하지 않고 1부터 시작하는 경우, 또는 반복문의 범위를 정확히 설정하지 않고 한 번 더 실행하거나 빠트리는 경우에 발생할 수 있다.

구현을 하다 보면 left<= right , left< right , left+ 1 < right 중 어느 걸 선택해야 할 지, 정답이 left인지 right 인지 (left+ right ) / 2인지 모르겠고, 심지어는 while문이 끝나지 않아서 시간초과를 받기도 한다.

구간 [left, right]가 Check(left) != Check(right)가 되도록 구간을 설정
while (left+ 1 < right)동안 mid = (left+ right) / 2에서
Check(mid) = Check(left)라면 left = mid, 아니라면 right = mid
구한 경계에서 답이 left인지 right인지 생각해보고 출력

구현에서 헷갈린다면 관련하여 설명한 글을 참고하자.

참고 자료

Algorithm, Structure

Algorithm binary search