Binary search and monotone answer · HTML
Maintain a closed interval [lo,hi] with the invariant: if target exists, it remains inside. Comparing a[mid] with target excludes one impossible side.
Recognition signals
- The input is globally sorted or has a detectable sorted half.
- Any occurrence of an exact value is sufficient; no first/last boundary is requested.
- One comparison decides which side can still contain the target.
- A linear scan works but logarithmic time is required.
False friends
| Signal | Why it is different |
|---|
| First-true boundary | For first or last occurrence, do not return on equality; preserve mid as a boundary candidate. |
| Binary search on answer | When feasibility is monotone but input is unsorted, the search domain is answer values, not array positions. |
Core invariant
At loop entry, an existing target lies inside closed interval [lo,hi]; every outside index has been disproved by sorted comparisons.
State, transition, and processing order
| Item | Definition |
|---|
| State | lo, hi, mid, and target; a closed interval is empty exactly when lo>hi. |
| Transition | If a[mid]<target set lo=mid+1; if greater set hi=mid-1; return immediately on equality. |
| Frontier / order | The contiguous interval of indexes not yet ruled out, rather than a queue or heap. |
Python skeleton
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
Correctness sketch
- Sortedness proves that when a[mid]<target, mid and everything left cannot match; the symmetric case removes the right side.
- Each update excludes mid, so the interval strictly shrinks and the loop terminates.
- Equality is an immediate witness; if the interval empties without equality, the invariant proves absence.
Complexity
| Time | Space | Parameters |
|---|
| O(log n) | O(1) | n is sequence length; every iteration removes at least half the remaining candidates. |
Edge cases
- For an empty array hi starts at -1 and the loop never runs.
- A singleton must handle both hit and miss.
- With duplicates, any matching index may be returned.
- Descending order requires reversed comparisons.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Using lo<hi with a closed interval | The last candidate may never be examined; exact closed search uses lo<=hi. |
| Failing to exclude mid | Updates lo=mid or hi=mid can loop forever on adjacent positions. |
| Blindly applying it to a rotated array | The whole array is not sorted; first identify which half is ordered. |
Selection and exclusion rules
- For any exact occurrence, the closed-interval template is direct.
- For a first or last occurrence, switch to binary-search-boundary.
- When updates are frequent and queries rare, paying to sort may not be worthwhile.
Original micro-example
| Part | Detail |
|---|
| Result | Return index 3. |
| Setup | Find 19 in sorted sequence [3,8,12,19,25]. |
| Trace | mid=2 gives 12, excluding the left half; new mid=3 matches. |
Recall prompts
My notes