[알고리즘] 이분 탐색

이분 탐색

정렬되어있는 배열에서, 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신, 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법
이분 탐색은 O(lonN)의 시간복잡도를 가지므로, 선형 탐색에 비해 빠르다는 장점이 있다.

특징

• 정렬된 배열을 기준으로 탐색을 진행한다.
• start와 end 변수가 존재한다. (처음에는 배열의 시작과 끝을 각각 가리킨다.)
• 범위를 절반으로 줄이기 위한 mid = (start + end) // 2 변수가 존재한다.
• mid를 기준으로 범위를 줄여나간다.
• 💡 탐색해야 하는 범위가 매우 클 때 이분 탐색을 고려하자.

예시

• arr[mid]를 기준으로 찾고자 하는 값보다 큰지, 작은지 판단한다.
• arr[mid]가 찾고자 하는 값보다 작다면 start = mid + 1
• arr[mid]가 찾고자 하는 값보다 크다면 end = mid - 1
• mid도 이에 따라 업데이트 해주다가, arr[mid]가 찾고자 하는 값이 된다면 성공한다.
• 만약 start와 end가 역전된다면, 찾는 값이 배열에 없는 경우라고 판단할 수 있다.

문제

1. boj 1920: 수 찾기(실버4)

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
test = list(map(int, input().split()))
arr.sort()

def BS(k):
    st, en = 0, n-1
    while st <= en:
        mid = (st + en) // 2
        if arr[mid] == k:
            return 1
        elif arr[mid] < k:
            st = mid + 1
        elif arr[mid] > k:
            en = mid - 1
    return 0

for k in test:
    print(BS(k))

2. boj 1654: 랜선 자르기(실버2)

import sys
k, n = map(int, sys.stdin.readline().split())
l = []
for _ in range(k):
    l.append(int(sys.stdin.readline()))

# upper bound
st, en = 1, sum(l) // n # st를 1로 설정해야 ZeroDivision 발생 안 함
while st <= en:
    mid = (st + en) // 2
    num = sum(list(i // mid for i in l))
    if num >= n: # 만족
        st = mid + 1
    else:
        en = mid - 1

print(en)

• 최댓값을 찾는 것이기 때문에, upper bound를 찾아주는 알고리즘으로 작성하면 된다.

주의사항

• 배열이 정렬되어 있어야 이분탐색을 사용할 수 있다.
• 무한루프에 빠지지 않도록 mid값을 설정해야 한다.