이진 탐색

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

이진 탐색(binary search)을 사전에서는 "검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘"이라고 정의하고 있습니다. 하지만 사전적 의미는 잘 와닿지 않으니, 한 가지 예시를 들어보겠습니다.

업다운 게임

import random
num = random.randrange(1, 101)
# num == 25 이라고 가정하겠습니다.

1부터 100까지의 자연수 중에서 이 num(25)를 맞추는데 최소 몇 번의 시도를 해야할까요?

완전 탐색을 기억해보면, 우리는 최악의 경우 100번의 시도를 해야합니다. 그렇기 때문에 시간 복잡도는 O(N)이죠.

하지만 이 고정된 num 값과 우리가 시도한 숫자의 대소 관계를 파악할 수 있다면 더 빠르게 num 값을 알아낼 수 있습니다. 업다운 게임을 생각하시면 됩니다. 해당 링크에 들어가서 한 번 해보세요 !

우리가 50 ! 을 외치면, num이 50보다 작다는 사실을 알게 되므로 51부터 100까지의 수는 정답의 범위에서 배제됩니다.

이처럼, 1~100까지의 수에서 우리가 원하는 수를 알기 위해서는 최대 7번만 시도하면 됩니다. 따라서 정렬된 상황에서 특정 수를 조회하는 시간 복잡도는 O(logN)입니다. 리스트가 아직 정렬되어있지 않아 정렬이 필요하다면, O(NlogN)의 시간 복잡도로 정렬한 후 이분탐색을 진행해주면 됩니다.

위의 상황을 코드로 나타내면 아래와 같습니다.

num = 25
left = 1
right = 100
while left <= right:
    mid = (left + right) // 2

    if mid == num:
        break
    elif mid < num:
        left = mid + 1
    elif mid > num:
        right = mid - 1

처음 수의 범위를 left ~ right로 설정하고, 조건에 맞게 범위를 좁혀가는 방식으로 진행됩니다.

그러다 left가 right를 넘어설 경우에 반복문은 종료됩니다.

upper bound, lower bound

이분 탐색의 핵심은 |-----------------ㅇ-----| 명확히 나누어지는 이 경계값 을 찾는 것입니다.

하지만 같은 숫자가 여러 번 존재하는 배열이라면 어떻게 숫자의 위치를 찾을 수 있을까요?

이는 upper bound와 lower bound 개념으로 이해할 수 있습니다.

파이썬 upper bound, lower bound
def lowerbound(array, k): # k 이상 값이 처음 나오는 위치
    left = 0
    right = len(array)

    while left < right:
        mid = (left + right) // 2

	# 📢 이 부분 주의!
        if array[mid] >= k: #오른쪽으로 좁힘 -> upperbound
            right = mid
        else:
            left = mid + 1

    return left
def upperbound(array, k): #k 초과 값이 처음 나오는 위치
    left = 0
    right = len(array)
    
    while left < right:
        mid = (left + right) // 2
		
        # 📢 이 부분 주의!
        if array[mid] > k:
            right = mid
        else:
            left = mid + 1

    return left  
    
lowerbound([0,1,2,4,4,4,7,8], 4) #3 return
upperbound([0,1,2,4,4,4,7,8], 4) #6 return

조금 더 생각해볼까요? 왜 lowerbound와 upperbound를 만족하는지 꼭 ! 직접 설명해볼 수 있을 때까지 이해하고 넘어가봅시다.

• lowerbound 로직 right = mid 로 할당하는 건 범위를 왼쪽으로 좁히는 것을 의미합니다. 이 때 array[mid]가 k랑 같아도 right=mid로 왼쪽으로 계속 좁히기 때문에 lowerbound를 만족시키게 됩니다.

• upperbound 로직 array[mid]가 k와 같거나 작을 때까지 left = mid+1로 계속 오른쪽으로 보냅니다. 따라서 left는 만족을 하게 되는 때가 오더라도 그 뒷 값을 가리키게 됩니다. 즉, upperbound를 만족시킵니다.

연습문제

BOJ 13423

https://www.acmicpc.net/problem/13423www.acmicpc.net

바로 이전의 완전 탐색 파트에서 다뤘던 문제입니다.

완전 탐색으로도 가능하지만, 이진 탐색 또한 풀이가 가능한 문제입니다.

참고로 해당 풀이는 pypy3에만 적용됨을 참고해주시기 바랍니다.

t = int(input())
for _ in range(t):
    n = int(input())
    li = sorted(list(map(int, input().split())))
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):   # 중복되는 인덱스가 없도록 i+1부터 시작
            left = i
            right = j
            val = (li[left] + li[right]) / 2    # 원하는 값
            while left <= right:
                mid = (left + right) // 2
                if val == li[mid]:
                    ans += 1
                    break
                elif val > li[mid]:
                    left = mid + 1
                elif val < li[mid]:
                    right = mid - 1
    print(ans)

이전에 해당 문제를 완전 탐색으로 접근할 때의 컨셉을 그대로 따라해봅시다.

일단 마찬가지로 두 점을 반복문을 통해 고릅니다. 완전 탐색에서는 첫 번째, 두 번째 점을 골랐으니 이번엔 첫 번째와 세 번째 점을 골라보도록 합시다.

각 점의 인덱스를 left, right로 지정하고, 우리가 원하는 중앙 값(val)이 리스트에 있는지만 확인해주면 됩니다.

같은 문제를 여러 방식으로 푸는 것도 많은 도움이 되니, 꼭 풀어보시길 바랍니다.

풀어볼 문제

이진탐색 또한 시간복잡도에 주의하며 문제를 풀어봅시다.

https://www.acmicpc.net/problem/16401www.acmicpc.net

16401

https://www.acmicpc.net/problem/17951www.acmicpc.net

17951

(cf. 17951 문제처럼 정렬을 하지 않아야하는 이진 탐색 문제도 있으니 유의하세요!)

https://www.acmicpc.net/problem/17179www.acmicpc.net

17179