[75 LeetCode] 번외 - 이진 탐색 정리

https://www.wikiwand.com/en/Binary_search_algorithm

Wikiwand - Binary search algorithm

 

이진탐색 관련 문제를 풀다가, 종종 이진탐색문제를 만날 때마다 헷갈려서 잘 정리된 문서를 찾아보았다.

경우에 따라 필요한 상세부분이 조금씩 다른데, 거기에 대한 정리가 잘 되어있다.

• exact match가 필요한 경우
  • leftmost 값이 필요한 경우
  • rightmost 값이 필요한 경우
• Rank가 필요한 경우
• Range가 필요한 경우
• 이전값/ 이후값이 필요한 경우 

등의 예시가 나와있다.

 

몇가지만 뽑아서 정리해봤다.

1) Exact Match

기본 틀

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

시작 범위: 0 ~ n-1
반복 조건: L <= R
중간값 소수점: 버림
A[mid] === T인 경우: return

아래와 같이 할 수도 있다.

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

반복조건: L != R
중간값 소수점: 올림
A[mid] === T인 경우: L := m

 

위 예시들은 중복값에 대해 중복값 중 아무 값의 인덱스를 반환한다. 중복값의 가장 왼쪽값이나 오른쪽값은 조금 다른 방식이 필요하다.

2) 매칭되는 값 중 가장 왼쪽 값 (Lower bound)

 

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

시작 범위: 0 ~ n
반복 조건: L < R
중간값 소수점: 버림
A[mid] === T인 경우: R := m

각 조건이 헷갈릴 수 있다. 하나씩 분석해보자.

시작 범위: left most index 값의 경우, 가장 작은 경우 0, 가장 큰 경우는 n이 된다. (A[n - 1]이 최대값인데 T가 해당 값보다 큰 경우)

while 내 조건문의 경우 m + 1, m, m - 1이 헷갈릴 수 있다. L, R이 최대로 이동할 수 있는 만큼의 범위를 생각해야한다.

A[m] < T인 경우, L이 오른쪽으로 이동해야하는데, T의 leftmost값은 항상 m보다 크다. m + 1로 L을 설정해줄 수 있다.
A[m] < T < A[m + 1]인 경우 확인해보면 T는 m 다음에 위치해야하므로 m + 1이 답이되기 때문에 m + 1을 포함하는 범위여야한다.
m + 1로 L을 세팅해줘도 유효한 범위가 되기 때문에 문제없다. 
(m으로 설정해 줄 경우 무한 루프가 될 수 있다.)

A[m] > T인 경우, R이 왼쪽으로 이동해야하는데, A[m - 1] < T < A[m]인 경우가 발생하면 리턴 값이 m이어야한다. 즉, m을 포함하는 범위어야 최대값인 m을 리턴할 수 있으므로 m - 1이 아닌 m으로 세팅해줘야한다.

A[m] === T일 때, R이 왼쪽으로 이동해야 leftmost를 찾을 수 있다. (같은 값 중 가장 왼쪽 값을 찾기 때문에)
위의 경우와 마찬가지로 A[m - 1] < A[m]인 경우, m이 답이므로 m을 포함하는 범위로 계산해줘야한다.

배열에서 현재 값의 랭크를 찾는 경우에도 위 알고리즘을 사용할 수 있다.
현재 값의 랭크는 현재값을 삽입할 인덱스를 찾는 것과 같다.
현재 값보다 작은 최대값을 찾는 것도 가장 왼쪽값을 찾는것과 같다. 가장 왼쪽값 - 1을 해주면 된다.

사실 exact match에서도 사용할 수 있으므로, 가장 많이 사용하는 예시인 것 같다.

 

3) 가장 오른 쪽 값

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

시작 범위: 0 ~ n
반복 조건: L < R
중간값 소수점: 버림
A[mid] === T인 경우: L := m + 1
return: R - 1

가장 왼쪽값을 찾을 때와 마찬가지로 조건을 하나씩 분석해보면 덜헷갈릴 수 있다.

 

 

이 외에도 이진탐색에 대한 성능, 다른 알고리즘과의 비교, 조금씩 다른 variation들 등 다양한 정보가 정리되어 있으므로 공부를 한다면 한 번 찾아보는 것도 좋은 것 같다.

맨위에 첨부한 Donald Knuth의 말처럼, 이진탐색 자체는 어렵지 않지만 이진탐색을 사용하면서 등호나 범위등의 디테일이 헷갈리는 것은 많은 사람이 겪는 일이다. 문제를 풀다가 막히더라도 괴로워하지말고 차근차근 정리해보자.