Binary Search

Efficiently finds target in sorted array by halving search space. Core idea: compare mid; discard half. Logarithmic growth in comparisons makes it foundational for higher-level searching, decision problems, and answer-space exploration.

Time

O(log n)

Space

O(1) iterative

Recurrence

T(n) = T(n/2) + O(1)

Mechanics

Compute midpoint mid = ⌊(lo+hi)/2⌋.
If arr[mid] == target: return mid.
If arr[mid] < target: lo = mid + 1 else hi = mid - 1.
Repeat while lo ≤ hi; return -1 if exhausted.

Recurrence & Properties

Recurrence: T(n)=T(n/2)+O(1) → O(log n).

Halving: Search interval size halves each iteration.

Monotonic Need: Requires sorted/monotonic predicate space.

Cost per step: Single comparison + pointer move.

Overflow safe: mid = lo + ((hi - lo) >> 1).

Variants: lower/upper bound, first true, binary on answer.

Applications & Tradeoffs

Applications

Lookup tables
Boundary finding
Optimization search

Advantages

Fast on large sorted data
Simple iterative form
Low memory

Disadvantages

Needs sorted data
Random access requirement
Edge cases off-by-one

Pattern: Divide-Search

Performance Notes

Binary searching the answer space generalizes to optimization via monotonic predicate.
On modern CPUs branch prediction affects constant factors; interpolation or exponential variants can reduce comparisons for specific distributions.
Cache-friendly due to logarithmic probes (but not strictly sequential like linear scan).

Theory Simulation

Quick Sort Maximum Subarray (D&C)