[알고리즘] 이진 탐색 (+LeetCode 33)

이진 탐색은 정렬된 배열에서 특정 원소를 찾는 알고리즘이다. 

동작 원리는 간단하다. 편의상 오른쪽 원소가 크거나 같다고 가정하자.

 

1. 배열의 중간에 위치한 값이 찾고자 하는 값보다 큰지 작은지 비교.
2. 중간에 있는 값이 더 크면 찾고있는 원소는 중간값의 왼쪽에 있을 것이다. 중간값의 왼쪽에 있는 원소로 배열을 만들어서 다시 1번을 시행한다. 중간에 있는 값이 더 작으면 중간값의 오른쪽에 있는 원소들로 다시 1번을 시행한다.

Pseudo code로 정리하면 다음과 같다 (pseudo code는 모두 위키피디아에서 가져왔다):

# A = [A0, A1, A2, ..., An-1]
# A0 <= A1 <= ... <= An-1
# n = len(A)
function binary_search(A, n, T) 
    L = 0 # list의 왼쪽 index
    R = n − 1 # list의 오른쪽 index
    while L ≤ R do 
        m = floor((L + R) / 2) # 중간 index
        if A[m] < T:
            L = m + 1 
        else if A[m] > T:
            R = m − 1 
        else: 
            return m 
    return unsuccessful

개념 자체는 쉽지만 문제가 바뀜에 따라 <=, >=,<,> 등등 헷갈리기 쉽다.

예를 들어서 찾고자 하는 값이 중복으로 존재하는 경우 가장 왼쪽에 있는 index를 찾고 싶다고 하자. 다음과 같이 바뀌어야 한다:

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

위에 소개한 알고리즘은 T가 A에 있다는 가정이 있다. T가 A에 없는 경우 (1) output이 len(A)-1를 초과하는지 (2) A[output] ==T인지 확인을 해야 한다.

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

이 경우도 T가 A에 없는 경우 예외 처리를 해줘야 한다. 비슷하게 (1) output이 0보다 작은지 (2) A[output]==T인지 확인을 해야 한다.

 

참고로 m = floor((L+R)/2)로 구현을 하면 잘못하면 overflow 현상이 발생할 수 있다 (L+R 이 현제 사용하고 있는 정수의 최대 표현 가능한 크기를 초과하는 경우). 따라서 실제로는 L+floor((R-L)/2)로 구현하는 것이 좋다.

 

이제 문제를 하나 풀어보자.

정렬되어 있는 배열을 2개로 쪼개고, 두 배열의 순서를 뒤바꿔서 다시 한 배열로 합친 배열이 주워졌을 때 타깃 값을 찾는 문제이다. 우선 쪼개진 위치를 (최소 값의 위치) 이진 탐색으로 찾고 이 위치를 기점으로 다시 이진 탐색을 하면 된다. 중복되는 수가 없기 때문에 조금 편하다.

쪼개진 위치를 제외하면 오른쪽으로 증가하는 배열이기 때문에 우선 왼쪽 값을 최소 값의 위치로 설정하고, 이진 탐색을 한다. 만약 중간 값이 L의 값보다 크면 최소 값이 오른쪽에 있을 수밖에 없기 때문에 L=m으로 설정한다. 만약 중간 값이 R의 값보다 작으면 최소 값은 왼쪽에 있기 때문에 R=m으로 설정한다. 만약 둘 다 아니면 최소 값은 m+1로 되는 것을 몇 가지 예시에 대해서 생각해 보면 알 수 있다. 

이렇게 최소 값의 위치를 찾으면 그 뒤로부터는 단순한 이진 탐색으로 풀 수 있다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        len_nums = len(nums)
        L=0
        R=len_nums-1
        min_val = L
        while L < R:
            m = (R-L)//2+L
            if nums[m] > nums[L]:
                L = m
            elif nums[m] < nums[R]:
                R = m
            else:
                min_val = m+1
                break
        L = min_val
        R = min_val + len_nums-1
        while L <= R:
            m = (R-L)//2 + L
            if nums[m%len_nums] < target:
                L = m+1
            elif nums[m%len_nums] > target:
                R = m-1
            else:
                return m%len_nums
        return -1

 Refs: 

https://en.wikipedia.org/wiki/Binary_search_algorithm