이진 탐색(Binary Search) 알고리즘

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

이진 탐색(Binary Search)이란?

정렬된 배열에서 특정한 값의 위치를 찾는 알고리즘이다. 절반씩 분할하여 탐색하므로 주어진 배열이 정렬된 상태임을 보장하면 속도가 매우 빠르다.

이진 탐색 동작

위 배열에서 5를 찾는다고 하자.

처음엔 left를 시작점, right를 배열의 끝에 두고 탐색 기준 좌표 mid를 그 절반으로 설정한다. 예시에선 left = 0, right = 12가 되어 mid = 0 + (12 - 0) // 2 = 6이 된다. mid 좌표의 값은 7이므로 찾고자 하는 값 5보다 작다. 따라서, 찾고자 하는 값은 mid보다 좌측에 있으므로 right를 mid - 1로 설정한다.

이후 새로이 설정된 left, right 기준으로 mid 값을 저하면 mid는 2가 되고 mid 좌표의 값이 3이 된다. 3 < 5이므로 찾고자 하는 값은 mid 좌표보다 우측에 있다. left를 mid + 1로 설정한다.

left, right가 3, 5이므로 mid는 4가 된다. 그리고 4번 좌표의 값은 5이므로 그대로 탐색을 종료하고 좌표 값을 반환한다. 전체 탐색 과정을 보면 값을 찾을 때까지 탐색 범위가 절반씩 줄어든다. 그리고 줄어들어도 범위에 대해 선형탐색하지 않고 중간 좌표만 탐색하기 때문에 시간복잡도는 $O(log\ n)$이다.

중간 좌표 설정 시 자료형 크기

보통 int 자료형 크기를 python에서 고려할 필요는 없겠지만 메모리를 항시 생각해야 하는 C계열 언어나 JAVA는 문제가 발생할 여지가 있다. 만약 중간 좌표를 산출하는데 단순히 (left + right) // 2를 적용하면 (left + right) 연산 시 자료형의 범위를 초과하여 에러를 출력할 수 있기 때문이다. 따라서, 중간 지점을 계산할 땐 left + (right - left) // 2로 하여 애당초 더해지는 값을 미리 줄이는 게 바람직하다.

python 코드

def BinarySearch(arr, val):
    left, right = 0, len(val) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == val:
            return mid
        elif arr[mid] < val:
            left = mid + 1
        elif arr[mid] > val:
            right = mid - 1
    return -1

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
print(f'value 5 index is {binarySearch(nums, 5)}')

중복된 배열에서의 이진 탐색

이진 탐색의 입력값이 중복값 없는 깔끔한 배열이라고 보장할 수 없다. 그러므로 중복된 원소가 존재할 경우 어떻게 탐색을 해야 하는지 고민해야 한다.

위 그림대로 원소의 값을 기준으로 lower bound와 upper bound를 제대로 설정할 수 있으면 찾고자 하는 범위를 명확히 나눌 수 있다.

Lower Bound

lower bound는 찾고자 하는 값과 같거나 처음으로 큰 값이 나오는 좌표를 의미한다. 만약 찾고자 하는 값이 존재하지 않다면 해당 값보다 큰 값들 중 가장 최소값의 좌표를 리턴한다.

Upper Bound

upper bound는 찾고자 하는 값보다 큰 값들 중 가장 처음으로 만나는 좌표를 의미한다. 즉, 찾고자 하는 값보다 큰 값들 중 최소값의 좌표와 동일하다.

python code

def binarySearchBound(arr, val):
    left = binaryLowerBound(arr, val)
    right = binaryUpperBound(arr, val)
    return left, right

def binaryLowerBound(arr, val):
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] >= val: # 타겟보다 좌표값이 크거나 같으면
            right = mid # 우측 조정
        elif arr[mid] < val: # 타겟보다 좌표값이 작으면
            left = mid + 1 # 좌측 조정
    return left # 하계는 타겟보다 같거나 큰 좌표이므로

def binaryUpperBound(arr, val):
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= val: # 타겟보다 좌표값이 작거나 같으면 
            left = mid + 1 # 좌측 조정
        elif arr[mid] > val: # 타겟보다 좌표값이 크면
            right = mid # 우측 조정
    return left # 상계는 타겟보다 큰 최소 좌표이므로

nums = [1, 1, 2, 2, 3, 3, 3, 4, 6, 6, 7, 8, 8, 9]
l_b, r_b = binaryBound(nums, 1)
print(f'lowerbound: {l_b}, upperbound: {r_b}, result: {nums[l_b:r_b]}')
print(binaryBound(nums, 1))
print(binaryBound(nums, 2))
print(binaryBound(nums, 3))
print(binaryBound(nums, 4))
print(binaryBound(nums, 5))
print(binaryBound(nums, 200))