/ ALGORITHM

이분 탐색

이분 탐색

알고리즘 문제에서 단골 문제로 등장하는 이분 탐색을 정리하려고 한다.

단순히 Target 을 찾는 것부터, Target 이 들어갈 자리(lower bound, upper bound)를 찾는 방법에 대해서도 한 번 정리해보자.

이분 탐색(Target과 동일한게 있을 때)

이분 탐색의 가장 기초적인 형태로, 찾고 싶은 Target 이 몇 번째 인덱스에 존재하는지 찾는 방법이다.

python
def simple_binary_search(target: int, arr: list):
    # 오름차순이라고 가정, 만약 arr 의 정렬이 보장되어 있지 않다면 정렬을 해야한다.
    arr.sort()

    start = 0
    end = len(arr) - 1

    while start <= end:
        mid = (start + end) // 2
        print(mid, arr[mid])

        if target > arr[mid]:
            start = mid + 1
        elif target < arr[mid]:
            end = mid - 1
        else:
            # target == arr[mid]
            return mid

    # target 을 찾지 못함
    return -

이분 탐색은 말 그대로, 이등분하여 탐색하는 알고리즘이다. 로직을 자세히 보아도 이해하는데 크게 어려움은 없다.

그렇다면 target 이상인 것 중에 가장 첫 번째 인덱스를 찾고 싶거나, target 보다 큰 것중에 가장 작은 인덱스를 찾는 방법을 알아보자.

Lower Bound

(target <= arr[idx]) target 보다 크거나 같은 것 중에 가장 첫 번째 인덱스를 찾고 싶다면 어떻게 해야할까?

python
arr = [1, 3, 5, 5, 5, 7, 9]
target = 5

# 원하는 정답 = 2 (5, 5, 5의 인덱스 중에서 가장 작은 인덱스)
# 위의 simple_binary_search() 함수의 결과값 = 3

def lower_bound_bisect(target: int, arr: list):
    # 오름차순이라고 가정, 만약 arr 의 정렬이 보장되어 있지 않다면 정렬을 해야한다.
    arr.sort()

    start = 0
    end = len(arr)

    while start < end:
        mid = (start + end) // 2
        print(mid, arr[mid])

        if target >= arr[mid]:
            end = mid
        elif target < arr[mid]:
            start = mid + 1

        """
        만약 target 보다 작다면, start 를 mid + 1 로 바꿔서 이분한 배열의 오른쪽만 다시 확인하게 하고
        만약 target 보다 크거나 같다면, mid 를 포함한 채로, 배열의 왼쪽을 다시 살펴본다.

        왜 mid - 1 이 아니라, mid 일까? -> 찾고 싶은 것이 `target 보다 크거나 같은 것` 이므로, target >= arr[mid] 를 만족하는 순간
        우리가 찾고자 하는 것이다. 그렇기 때문에 정답 범주에 넣어두어야 한다.
        """
    return start

Upper Bound

이번에는 target 보다 큰 것 중에, 가장 작은 인덱스 값을 알아보자.

python
arr = [1, 3, 5, 5, 5, 7, 9]
target = 5

# 원하는 정답 = 5 (1, 3, 5, 5, 5까지는 target 보다 작거나 같은 값이고, 7부터 target 보다 큰 값이므로)

def upper_bound_bisect(target: int, arr: list):
    # 오름차순이라고 가정, 만약 arr 의 정렬이 보장되어 있지 않다면 정렬을 해야한다.
    arr.sort()

    start = 0
    end = len(arr)

    while start < end:
        mid = (start + end) // 2
        print(mid, arr[mid])

        if target > arr[mid]:
            end = mid
        elif target <= arr[mid]:
            start = mid + 1
        """
        만약 target 보다 작거나 같다면, start 를 mid + 1 로 바꿔서 이분한 배열의 오른쪽만 다시 살펴보게 하고
        만약 target 보다 크다면, mid 를 포함한 채로 왼쪽을 다시 살펴보게 한다.

        왜 mid - 1 이 아니라, mid 일까? -> 찾고 싶은 것이 `target 보다 큰 것` 이므로, target > arr[mid] 를 만족하는 순간
        우리가 찾고자 하는 것이다. 그렇기 때문에 정답 범주에 넣어두어야 한다.
        """
    return start

차이점

단순 이분 탐색과 lower / upper bound 의 while 종료 조건 차이점을 살펴보자.

while start <= end 와 while start < end 이 있는데, Lower/Upper 탐색은 1캰씩 움직이며 찾아나가는데 start <= end 로 하게 되면 소수점 버림으로 인해서 무한 루프에 빠질 수 있다.

또한 Lower/Upper 의 return 은 mid 가 아니라 start 인데, 이는 당연하게도 Lower 과 Upper 이 각각 크거나 같은 것 중에 최소값, 큰 것 중에 최소값을 return 해야하기 때문이다.

Lower/Upper 의 end 초기값도 조금 다른데, len(arr) - 1 이 아니라, len(arr) 이다. 이는 조건을 만족하는 곳이 없으면 무조건 len(arr) 의 위치에 넣으면 되기 때문이다.