판단표

비교식 하나가 반환 의미를 바꾼다

lower_bound와 upper_bound는 구조가 같지만, mid를 버리는 기준이 다릅니다. 표로 비교하면 오프바이원을 줄일 수 있습니다.

패턴

참일 때 버리는 쪽

거짓일 때 남기는 후보

반환 의미

lower_bound
arr[mid] < target

mid와 그 왼쪽은 target보다 작으므로 lo = mid + 1

mid가 첫 이상일 수 있으므로 hi = mid

첫 번째 >= target

upper_bound
arr[mid] <= target

mid까지는 target 이하이므로 lo = mid + 1

hi = mid 유지

첫 번째 > target

firstTrue
ok(mid)

mid가 참이면 더 왼쪽 첫 참을 찾기 위해 hi = mid

mid가 거짓이면 답은 오른쪽이라 lo = mid + 1

단조 판정의 첫 참

함수명을 먼저 정하기

첫 이상인지 첫 초과인지 이름으로 고정하면 비교 연산자를 덜 헷갈립니다.

mid가 답 후보일 수 있는 분기에서는 반드시 hi = mid 로 남깁니다.

조건을 만족하는 값이 없으면 n을 반환할 수 있어야 반열린 구간이 완성됩니다.

값 2의 구간은 [lower_bound(2), upper_bound(2)) 입니다. 예제에서는 [1, 4) 이므로 개수는 3입니다.

count = upper - lower