[알고리즘] 이진탐색 구현 방법

최근들어 이진탐색 문제를 많이 풀어보았는데 뒤죽박죽 섞여있는 개념들을 한번 정리하고자 글을 작성합니다. 개념적인 부분보다는 코드적인 구현방법을 정리합니다. 언어는 파이썬 입니다

이 글에서 정리하는 것

이진탐색 구현 방법

1. 재귀
2. while 문
   1. lower bound
   2. upper bound

구현 방법

재귀로 구현하기

arr = [10,20,30,60,80,110,120,150]

def binarySearch(left,right,target):
    mid = (left+right) // 2
    if target > arr[mid]:
        return binarySearch(mid+1,right,target)
    elif target < arr[mid]:
        return binarySearch(left,mid-1,target)
    elif target == arr[mid]:
        return mid

binarySearch(0,len(arr)-1,30)

arr[mid] 와 target을 비교해나가며 재귀적으로 수행합니다.
target이 크면 범위를 큰 쪽으로 줄여야하기 때문에 left = mid +1로 잡습니다. 반대라면 right = mid - 1로 범위를 작은 쪽으로 좁힙니다

재귀적으로 구현하면 해당 타겟이 반드시 존재한다는 가정하에 구현됩니다. 위 문제에서 배열에 존재하지않는 타겟을 탐색한다면 무한루프에 빠지고 맙니다.

만약 target 보다 큰 첫번째 인덱스를 구하라와 같은 문제가 주어진 경우에는 어떻게 해야할까요?

while문으로 구현하기

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

• while문으로도 비슷한 로직을 통해 이진탐색 결과를 구할 수 있습니다.
• 하지만 위의 식 역시 target이 반드시 배열에 존재해야만 사용할 수 있습니다.
• 배열에 존재하지 않는 경우에는 lower 또는 upper bound 알고리즘을 사용할 수 있습니다

lower bound

찾고자 하는 값보다 큰 값이 처음으로 등장하는 인덱스

arr = [10,20,30,30,30,30,60,80,110,120,150]

def binarySearch(target):
    left = 0
    right = len(arr)
    while left < right:
        mid = (left + right) // 2
        if target <= arr[mid]:
            right = mid 
        elif target > arr[mid]:
            left = mid + 1
    return right

print(binarySearch(25)) # 2

기존의 binarySearch와 다른 점이 있습니다

1. right = len(arr)
2. if target <= arr[mid]
3. return right

저는 사소한 부분에서 코드가 조금씩 바뀌었기 때문에 처음에는 매우 헷갈렸는데요. 차근차근히 살펴보도록 하겠습니다.

arr1 = [10,20,30,30,30,40,50,60] 
arr2 = [10,20,30,30,40,40,50,60]

위 두 배열에서 taget=30인 경우를 생각해봅시다.

1. arr1배열에서 arr1[4] == 30 으로 target을 바로 찾아 버렸습니다.
2. 하지만 이전 인덱스에 30 값이 존재하기 때문에 원하는 값이 아닙니다.
3. 이러한 경우에 계속해서 탐색해야합니다
4. 마찬가지로 arr2배열에서 if target < arr[4] 이므로 계속해서 탐색을 해야합니다
5. 즉 , if target <= arr[mid] 인 경우 right를 좁혀 탐색을 계속 해야합니다
6. if target > arr[mid]인 경우 left = mid+1로 설정해도 아무 상관이 없습니다 (잘 생각해보세요!)

계속해서 탐색을 하기전에, right = mid로 보험을 듭니다

만약 arr1배열이 만약 아래와 같다면 어떻게 될까요?

arr1 = [10,20,25,27,30,40,50,60] 

1. right = mid -1 로 했다가는[10,20,25,27] 배열내에서 30을 찾으려고 할겁니다
2. right = mid로 이전에 찾았던 target도 포함한 [10,20,25,27,30] 내에서 값을 다시 찾아야합니다
3. 정리하자면, right를 조정하여 범위를 좁히기 전, 이전 탐색에서 찾았던 target을 포함하여 탐색합니다.

lower bound의 핵심은 target을 포함한 right (right=target)을 계속해서 줄여나가며 탐색하는 것입니다

그렇다면 upper bound는 반대로 target을 포함한 left (left=target)을 계속해서 늘여나가며 탐색하는 것이겠죠?

arr = [10,20,30,30,30,30,60,80,110,120,150]

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

print(binarySearch(30)) #5

• 마찬가지로 if target == arr[mid]인 경우에는 mid 값을 포함한 채로 left를 조절해야합니다