경계 탐색 순서

규칙을 먼저 고정하면 경계는 같은 방향으로 수렴합니다

값 하나를 찍는 것이 아니라, 같은 기준으로 탐색 구간과 판정 결과를 끝까지 밀어붙이는 과정입니다.

1 구간 규칙 고정

먼저 한 표기만 선택합니다

[lo, hi)처럼 시작 전에 규칙을 정해 두면, 설명과 코드가 같은 의미를 유지해 경계가 흔들리지 않습니다.

정답 후보는 항상 [lo, hi) 안에 있다
2 단조성 확인

판정은 한 번만 바뀌어야 합니다

ok(x)가 인덱스가 커질수록 한 번만 뒤집혀야 경계가 생기고, 절반을 안전하게 버릴 수 있습니다.

false false false | true true true
3 같은 규칙 유지

mid 갱신도 같은 약속으로 처리합니다

참이면 왼쪽 경계를 남기고, 거짓이면 오른쪽으로 넘겨야 같은 불변식이 반복마다 유지됩니다.

if ok(mid): hi = mid else: lo = mid + 1
반복이 끝날 때까지 남겨야 할 약속

lo <= ans < hi가 계속 성립하면 오프바이원과 무한 루프를 줄이고, 마지막 lo를 경계값으로 안전하게 반환할 수 있습니다.