경계 불변식 점검표

경계 탐색 불변식 점검표

이진 탐색은 mid 계산보다 버린 구간의 의미를 반복마다 유지하는지가 핵심입니다.

단조성

판정 결과가 한 번만 바뀐다

false 구간과 true 구간이 섞이면 절반을 버리는 판단이 성립하지 않습니다.

구간 표기

[lo, hi)로 끝까지 유지

닫힌 구간과 반열린 구간을 섞지 않아야 종료 조건과 반환 위치가 흔들리지 않습니다.

반환 의미

찾은 위치와 삽입 위치 분리

lower_bound, upper_bound, firstTrue가 답 없음에서 무엇을 돌려주는지 먼저 정합니다.

경계 탐색 불변식 최종 기록

lower arr[mid] < target이면 mid까지 버리고 lo를 오른쪽으로 보냅니다.
upper arr[mid] <= target 조건을 써서 같은 값의 끝 다음 위치를 찾습니다.
firstTrue 판정 함수의 단조성을 작은 답 공간으로 직접 출력해 확인합니다.