How Does Binary Search Find the First or Last Equal Index?
Boundary binary search records a match and continues on one side. Inclusive bounds must move past mid so the candidate range strictly shrinks.
With duplicates, finding any match is not enough. Save a matching index, then continue left for the first match or right for the last. The invariant remains: if a better answer exists, it lies in the inclusive range [low, high].
First equal
Press Run to execute this example. Use console.log to print a value.
For [1, 2, 2, 2, 3], the first middle is index 2. Save it and search [0, 1]; index 1 also matches, so save 1 and search left once more. The final answer is 1.
Correctness, cost, and conventions
After a match at middle, no index to its right can be a better first occurrence. Excluding the saved middle is safe because its index is retained in answer. Each update removes at least one index, proving termination. Time is O(log n) and extra space is O(1).
- Empty input starts with
high = -1and returns-1. - A last-equal search changes the match update to
low = middle + 1. - Inclusive search stops at
low > high; half-open lower-bound search uses different initial bounds and a different stop. - Leaving a bound at
middlecan repeat the same range forever. - Sorted order is the fact that makes half-discarding safe.
Optional enrichment
Implement a half-open lower bound on [low, high) with high = values.length. It can return values.length as an insertion position; explain why that is not an out-of-bounds read.