Binary Search
Searching a sorted array by discarding half at every probe
The optimal guessing strategy
In a sorted array, comparing the target with the middle value tells us which half cannot contain the answer. Binary Search keeps a closed candidate range [lo, hi], probes mid, and removes one impossible half while preserving the other.
Two complete outcomes
The player first finds 17, then searches for the absent value 4. Bright bars remain candidates; dimmed bars have already been ruled out. The second run ends with lo > hi, which is a proof that no candidate remains, not a signal to scan again.
Search for target 17 in the sorted array; start with range [0, 9].
Invariant and cost
Invariant: if the target exists, it remains inside
[lo, hi].Safe midpoint: use
lo + ((hi - lo) >> 1) when integer overflow matters.Cost: the range halves each time, so lookup takes
O(log n) comparisons. The same invariant-driven template powers lower bounds, upper bounds, rotated-array search, and binary search over an answer space. The important skill is defining exactly what the candidate interval means before writing the loop.