이진 탐색

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

이진 탐색(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 upperbound(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 lowerbound(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) #7 return

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

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

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

연습문제

BOJ 13423

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

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

참고로 해당 풀이는 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)이 리스트에 있는지만 확인해주면 됩니다.

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

풀어볼 문제

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

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

Previous완전 탐색Next완전탐색 (백트래킹)

Last updated