[Algorithm] 이진 탐색 (Binary Search)

이진 탐색(Binary Search)는 말 그대로 반으로 쪼개면서 탐색하는 방법입니다.

이 때, 이진 탐색 대상(리스트은 반드시 정렬되어 있어야만 사용할 수 있습니다.

 

이진 탐색은 순차 탐색과 달리 시작점, 끝점, 중간점 변수 3개를 이용합니다.

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정입니다.

 

정렬된 데이터에서 이진 탐색 방법으로 숫자 4를 찾는 과정은 다음과 같습니다.

 

순차 탐색은 처음부터 끝까지 탐색하기 때문에 시간복잡도는 O(N)이지만, 이진 탐색은 단계마다 2로 나누므로 시간복잡도는 O(LogN)입니다.

코딩테스트에서는 보통 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제를 접근해야 주어진 시간안에 해결할 수 있습니다.

 

이진 탐색은 다음과 같이 구현할 수 있습니다.

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

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

    return None


n = 10
target = 7
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

result = binary_search(array, target, 0, n-1)
if result is None:
    print('찾는 값이 없음')
else:
    print(f'Index: {result}')

이진 탐색 과정 중 각 변수 상태 변화는 다음과 같습니다.

step	start	end	mid	array[mid]	target
1	0	9	4	9	7
2	0	3	1	3	7
3	2	3	2	5	7
4	3	3	3	7	7

 

코딩테스트에서 이진 탐색은 파라메트릭 서치(Parametric Search) 유형으로 자주 출제됩니다.

여기서 파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법입니다.

예를 들어 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 등이 있습니다.

 

관련된 문제 '떡볶이 떡 만들기'를 Binary Search를 이용하여 풀어보겠습니다.

<문제>

<해설>

<구현>

def solution(n, m, array):
    # 이진 탐색을 위한 시작점과 끝점 설정
    start = 0
    end = max(array)

    # 이진 탐색 수행 (반복적)
    result = 0

    while(start <= end):
        total = 0
        mid = (start + end) // 2
        for x in array:
            # 잘랐을 때의 떡볶이 양 계산
            if x > mid:
                total += x - mid
        # 떡볶이 양이 부족한 경우 더 많이 자르기 (오른쪽 부분 탐색)
        if total < m:
            end = mid - 1
        # 떡볶이 양이 충분한 경우 덜 자르기 (왼쪽 부분 탐색)
        else:
            result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
            start = mid + 1

    return result


n = 4
m = 6
array = [19, 15, 10, 17]

result = solution(n, m, array)
print('result: {}'.format(result))

참고: https://www.youtube.com/watch?v=94RC-DsGMLo&t=942s