이분탐색의 핵심은
양끝(lo, hi) 중 하나는 주어진 조건을 만족시키는 값, 다른 하나는 만족시키지 못하는 값으로 설정하여서 lo와 hi의 차이가 딱 1이 될 때까지 이분탐색을 계속하는 것
이다. 이런 방식이면 가능한 값 중에 경계값을 찾을 수 있다. 여기서 경계값이라함은 보통 문제에서 찾으라고하는 최댓값 혹은 최솟값을 의미한다.
코드 구현
나는 주로 아래와 같은 코드를 사용하여 이분탐색 알고리즘을 풀었다. 언어는 파이썬을 사용했다.
lo = # 확실하게 주어진 조건을 만족시키는 경우의 값
hi = # 확실하게 주어진 조건을 만족시키지 못하는 경우의 값
while lo + 1 < hi: # lo와 hi의 차이가 정확히 1이 될 때까지 반복
mid = (lo + hi) // 2
if: # 가능했던 경우
lo = mid # lo에 mid를 대입한다
else: # 불가능했던 경우
hi = mid # hi에 mid를 대입한다
print(lo) # 경계값을 대입받은 lo를 출력한다.가능한 경우가 hi였다면 lo와 hi의 역할이 바뀌고 마지막 print는 print(hi)를 해주면 된다.
보통,
- 최솟값을 찾는 경우라면
hi가 가능한 경우가 된다 - 최댓값을 찾는 경우라면
lo가 가능한 경우가 된다
