boundary guard
반환 위치는 마지막 배열 상태로 검증한다
구현 전후에는 전제, 구간, 갱신, 반환을 말로 확인하지 말고 작은 배열에서 후보가 어떻게 남는지 확인한다.
false 구간
true 구간
mid
반환 위치
예: 첫 번째로 6 이상인 위치 찾기
10
21
42
53
64
65
96
127
전제배열은 정렬되어 있고 `x >= 6` 판정은 한 번 false에서 true로 바뀐다.
구간`[lo, hi)` 안에 답을 보존한다. 버리는 쪽은 더 이상 답이 될 수 없다.
갱신`arr[mid] >= 6`이면 `hi = mid`, 아니면 `lo = mid + 1`이다.
반환반복 종료 후 `lo`는 첫 true, 즉 첫 번째 6 이상 위치다.
| 반례 | 확인할 반환 | 잡아내는 실수 |
|---|---|---|
| 모두 작음 | `n`을 반환한다. | `hi` 초기값을 `n - 1`로 두어 마지막 후보를 잃음 |
| 모두 큼 | `0`을 반환한다. | 참인 `mid`를 버려 첫 위치를 지나침 |
| 중복 경계 | 첫 번째 6의 인덱스 `4`를 반환한다. | 첫 값이 아니라 아무 6이나 반환 |