Binary Search

Repeatedly halve the search space by comparing the midpoint to the target, achieving O(log n) on sorted or monotonically ordered input.

Repeatedly halve the search space by comparing the midpoint to the target, achieving O(log n) on sorted or monotonically ordered input.

The target, if present, always lies within [left, right]; every boundary update guarantees the target is not in the discarded half.

Sorted order guarantees the target is entirely to the left or right of any midpoint — one comparison eliminates half the remaining candidates.

Each step halves the window, giving O(log n) total comparisons for any input size.