이분탐색 : 이진탐색 : Binary Search 틀/템플릿

# mid 라는 값으로 주어진 문제를 해결할 수 있는지 확인
def is_possible(mid):
    pass

# 이분탐색을 진행할 구간 지정
lo = 0
hi = 1e9
answer = lo


# 이분탐색 start
# 1] 최대중에 최소 찾기 -> 가능하면 범위를 낮춰가기
while lo <= hi:
    mid = (lo + hi) // 2
    
    if is_possible(mid):
        answer = mid
        hi = mid - 1
    else:
        lo = mid + 1
# 2] 최소중에 최대 찾기 -> 가능하면 범위를 높혀가기
while lo <= hi:
    mid = (lo + hi) // 2
    
    if is_possible(mid):
        answer = mid
        lo = mid + 1
    else:
        hi = mid - 1
        
# 정답 출력
print (answer)

문제 지문에 "최소값 중 최대를 찾아라" 혹은 "최대중에 최소를 구해라"

 

https://www.acmicpc.net/blog/view/109