이진 탐색 경계

이진 탐색 반환 의미

`lower_bound`, `upper_bound`, 첫 참 위치는 모두 경계 탐색입니다. 구간 표현과 반환 의미를 한 문장으로 고정하면 오프바이원을 줄일 수 있습니다.

구간 표현

`[lo, hi)` 또는 `[lo, hi]` 중 하나만 끝까지 사용합니다.

혼용 금지

판정 단조성

`false...true`처럼 결과가 한 번만 바뀌는지 반례로 확인합니다.

경계 존재 조건

갱신 규칙

`mid`가 후보인지 버릴 값인지에 따라 `lo`와 `hi`를 움직입니다.

무한 루프 방지

반환 위치

첫 `>=`, 첫 `>`, 첫 `true` 중 무엇을 돌려주는지 함수명에 남깁니다.

의미 보존