BINARY SEARCH

값 찾기보다 경계 불변식을 먼저 고정한다

이진 탐색은 단조 판정이 한 번 바뀌는 지점을 찾는 도구다. 구간 규칙을 섞으면 오프바이원이 생긴다.

F
F
F
T
T
T
T

목표는 첫 T 또는 마지막 F처럼 의미 있는 경계를 찾는 것이다.

단조성

한 번만 바뀐다

판정 결과가 F에서 T로, 또는 T에서 F로 한 번만 전환되어야 한다.

불변식

답은 구간 안

반복 후에도 정답 후보가 현재 탐색 구간에 남아야 한다.

갱신

규칙 하나 유지

닫힌 구간과 반열린 구간 템플릿을 섞지 않는다.

mid: 구간을 반드시 줄여야 한다.
ok(x): 가능/불가능 정의를 먼저 쓴다.
return: 찾는 경계가 lo인지 hi인지 고정한다.