Binary Search 헷갈리지 않게 구현하기 2

[obzva]

안녕하세요 2기에 참여하게 된 Flynn이라고 합니다
디스코드에도 공유했던 내용인데, 자료공유에 업로드되면 더 좋을 것 같다는 의견을 주셔서 여기에도 남겨두겠습니다 :D

들어가기 전에

1기 @Invidam 님께서 공유하셨던 Binary Search 헷갈리지 않게 구현하기를 반드시 일독하시길 추천드립니다.

• 키워드: 경계, 결정 문제, 이분적인 분포

개요

Binary Search 헷갈리지 않게 구현하기는 while (lo + 1 < hi)를 이용하여 Binary Search 알고리즘의 진행 및 결과값으로의 도달 과정을 이해하기 쉽게 설명하고 있습니다.
하지만 while (lo + 1 < hi)를 실제 문제 풀이에 적용하려면 아래와 같은 예외 조건들을 고려해야 합니다.

• f(begin) == f(end)인 경우 (주어진 배열에 대한 결정 문제의 결과값이 이분적으로 분포하지 않는 경우)
• 배열의 길이가 3 미만인 경우
  Binary Search 문제 풀이를 하면서 제 개인적으로 가장 많이 썼던 조건문은 while (lo < hi) 인데요, 이 글에서는 원 글의 개념을 이해한 채 while (lo < hi)를 편하게 잘 쓰기 위한 방법을 소개하겠습니다.

본문

아래와 같은 함수 f와 배열 A가 있다고 가정합니다.
f: 주어진 인자에 대해 T 혹은 F를 반환하는 함수
A: A의 원소 x에 대한 f의 결과값이 이분적으로 분포하는 배열

i 0 1 2 3 4 5 6 7 8 9
A T T T T T F F F F F

이 때, 두 가지 조건을 추가하면 저번보다 훨씬 간편하게 이진탐색을 구현할 수 있습니다.

  lo                   hi
i 0 1 2 3 4 5 6 7 8 9 (10)
A T T T T T F F F F F (F)

실제로 A의 길이는 10이고 인덱스는 9까지만 존재하지만 가상의 인덱스 10을 가정하고 hi의 초기값을 10으로 설정합니다.
또한 가상의 인덱스에 대한 f의 결과값은 배열의 이분적인 분포를 해치지 않게끔 설정합니다. (여기선 f(hi) = f(10) = F)

경계조건 lo < hi가 지켜지는 동안 while 문 안에서는 다음과 같은 연산을 진행합니다.

while lo < hi:
    mid = (lo + hi) // 2
    if f(mid):
        lo = mid + 1
    else:
        hi = mid

lo == hi가 되며 while 문을 탈출했을 때, 아래처럼 f(x_i) == F가 되는 첫번째 x_i에 lo와 hi가 위치함을 알 수 있습니다.

            lo
            hi        
i 0 1 2 3 4 5 6 7 8 9 (10)
A T T T T T F F F F F (F)

f의 결과값이 이분적으로 분포하지 않는 배열에 대해서도 아래처럼 결과가 동일하게 나타납니다.

                      lo
                      hi        
i 0 1 2 3 4 5 6 7 8 9 (10)
A T T T T T T T T T T (F)

  lo
  hi             
i 0 1 2 3 4 5 6 7 8 9 (10)
A F F F F F F F F F F (F)

이분 탐색이 완료된 이후에는 풀고 계신 문제에 따라 lo 혹은 hi 값을 적절히 사용하시면 됩니다.
아래는 python으로 구현한 코드입니다.

A = [True, True, True, True, False, False, False]
B = [True, True, True, True, True, True, True]
C = [False, False, False, False, False, False]

def binary_search(array):
    lo, hi = 0, len(array)
    while lo < hi:
        mid = (lo + hi) // 2
        if array[mid]:
            lo = mid + 1
        else:
            hi = mid
    return lo

print(binary_search(A)) # 4
print(binary_search(B)) # 7
print(binary_search(C)) # 0

맺음

저는 풀어본 알고리즘 문제 수가 꽤 됨에도 불구하고 Binary Search의 경계 조건 설정과 lo, hi의 결과값이 늘 헷갈렸습니다.
실제 Coding Interview에서도 Binary Search를 이용해서 기존의 풀이를 최적화해야하는 상황이 있었는데, 그 때도 이런 헷갈림 때문에 자신 있게 대답하지 못하고 탈락했던 기억이 있네요.
소개드린 Binary Search 헷갈리지 않게 구현하기를 읽고 나서는 Binary Search를 좀 더 정확히 이해할 수 있게 되었고 (이전까지는 그냥 숫자 크기 비교하는 알고리즘의 일종으로 생각했습니다), 좀 더 자신 있게 해당 알고리즘을 사용할 수 있었습니다.
긴 글 읽어주셔서 감사드리고 여러분께 도움이 되었으면 좋겠습니다 :D

(이 글은 제 블로그의 게시물을 기반으로 작성하였습니다)