경계 탐색

값을 찾기 전에 경계 정의

이분 탐색은 가운데를 찍는 기술이 아니라, 답 후보가 남아 있는 구간을 반복마다 유지하는 불변식 설계입니다.

단조성

한 번만 바뀌는가

판정 결과가 F에서 T로, 또는 T에서 F로 한 번만 전환되어야 절반을 버리는 판단이 안전합니다.

불변식

답은 구간 안에 있는가

반복이 끝날 때마다 정답 후보가 현재 구간 안에 남는다는 약속을 유지해야 합니다.

갱신

규칙 일관성

반열린 구간과 닫힌 구간 템플릿을 섞지 않고, 반환 의미까지 같은 규칙으로 맞춥니다.

mid 매 반복에서 구간을 반드시 줄이는 위치여야 합니다.
ok(x) 가능과 불가능의 의미를 코드보다 먼저 문장으로 씁니다.
반환 경계 만난 경계가 lo인지 hi인지 함수명과 맞춰 둡니다.