이분 탐색이란?
이분탐색은 결정 문제(Decision Problem)의 답이 이분적으로 분포할 때 사용할 수 있는 탐색 기법입니다.
정렬된 배열에서 사용하는 이유도 답의 분포가 이분적이여야 하기 때문입니다.
결정 문제란?
답이 Yes or No인 문제를 의미하며 보통 이분 탐색 문제에서는 1개의 매개변수를 가집니다.
예를 들어 1~50까지 수가 적힌 카드가 오름차순 정렬되어 있을 때, 특정 수 23이 적힌 카드를 찾는 문제가 있을 때 이를 결정 문제로 바꿔 생각해보면, i 번째 카드가 23보다 크냐?로 생각해 볼 수 있습니다.
이때 i에 따른 정답의 분포가 23을 기점으로 False, True의 분포가 이분적으로 나뉘는 것을 알 수 있다.
구현
- [lo, hi]가 Check(lo) != Check(hi)가 되도록 구간을 설정
- while (lo + 1 < hi)동안 mid = (lo + hi) / 2에서 Check(mid) = Check(lo)라면 lo = mid, 아니라면 hi = mid
- 구한 경계에서 답이 lo인지 hi인지 생각해보고 출력
이제 lo + 1 < hi인 동안 [lo, hi]를 [lo, mid] 또는 [mid, hi]로 줄여나가는데, 이 경우 Check(lo), Check(hi)는 바뀌지 않습니다. 이유는 Check(lo) == Check(mid)라면 lo = mid를, Check(hi) == Check(mid)라면 hi = mid를 하기 때문입니다. 또한 lo + 1 < hi이기 때문에 lo와 hi의 사이에는 무조건 한 개 이상의 칸이 있으며, mid는 항상 lo < mid < hi를 만족합니다. 따라서 구간의 길이는 매번 절반씩 줄어들며 언젠간 lo + 1 == hi가 되어서 반복문을 탈출하게 됩니다.
(반복문을 탈출했다면 lo + 1 >= hi인데 lo < mid < hi인 mid를 대입하기 때문에 lo < hi이고, 두 조건을 만족하는 lo, hi는 lo + 1 == hi인 경우밖에 없습니다)
def binary_search(arr,target):
# 정답의 범위에 대해 생각해보세요! -> low + 1 = high이고 high를 return 하고 있다는 점!
# 정답의 범위는 index:0~len(arr)-1
low = -1
high = len(arr)-1
while low + 1 < high:
mid = (low+high) // 2
if arr[mid] >= target:
high = mid
else:
low = mid
if arr[high] == target:
return high
else:
return -1
print(binary_search([1,2,5,6,10,15],10))이분 탐색 응용 lower bound, upper bound
1) lower_bound(v, v + n, x) := v[i - 1] < x <= v[i]인 i를 반환. (v[i] >= x인 i의 최솟값과 동치)
2) upper_bound(v, v + n, x) := v[i - 1] <= x < v[i]인 i를 반환. (v[i] > x인 i의 최솟값과 동치)
def LowerBound(arr,target):
low = -1
high = len(arr)-1
while low + 1 < high:
mid = (low+high) // 2
if arr[mid] >= target:
high = mid
else:
low = mid
return high
def UpperBound(arr,target):
low = -1
high = len(arr)-1
while low + 1 < high:
mid = (low+high) // 2
if arr[mid] > target:
high = mid
else:
low = mid
return high많이 하는 실수
- lo, hi는 항상 정답의 범위를 나타낼 수 있도록 해야한다. lo + 1 = hi 이기 때문에!
- 오버플로우 조심, 보통 문제에서 주어진 수의 범위가 엄청 크다.
- Check함수 구현을 잘 해야함
