Binary Search

Binary Search on Sorted Data

Halve a sorted range to find a target or a boundary (first/last position, insertion point).

Easy, about 60 minutes to practise.

1Understand

The idea

On sorted data, compare with the middle element and discard the half that cannot contain the answer, so n elements need about log₂ n steps. Most bugs come from the boundaries: decide whether you are looking for a value, the first position where a condition becomes true, or the last, and keep the loop invariant consistent with that choice.

Intuition

On sorted data, compare with the middle element and discard the half that cannot contain the answer. Roughly log₂ n steps beat a linear scan.

Most bugs come from boundaries: are you finding an exact value, the first position where a condition becomes true, or the last? Pick a loop invariant and stick to it; usually lo is inclusive, hi exclusive, or both inclusive with clear mid bias.

When duplicates exist, decide whether you want any hit or the leftmost/rightmost.

What you will be able to do

  • Pick consistent bounds ([lo, hi) or [lo, hi])
  • Find boundaries, not just equality

When to use it

  • Sorted array and a target
  • O(log n) required
  • First or last occurrence, insertion point
  • Rotated sorted array

2See it

Walkthrough

Find a value in sorted data

nums = [1, 3, 5, 7, 9, 11], target = 7, discard half each step.

1 / 6

LRM
1
3
5
7
9
11
012345
L → index 0R → index 5

Sorted nums, target 7. Invariant: answer lies in [left, right] if it exists.

left, right = 0, len(nums)-1

Live template

Line 1 active

1lo, hi = 0, len(a) # search in [lo, hi)
2while lo < hi:
3 mid = (lo + hi) // 2
4 if a[mid] < target: lo = mid + 1
5 else: hi = mid
6return lo

Complexity: time O(log n), space O(1)

O(log n) time, O(1) space. Linear scan is O(n), fine for tiny n, wrong for n ~ 10⁵ on a hot path. If the array is unsorted, binary search on indices does not apply (use binary search on the answer instead, or sort first).

Read the walkthrough as text

Lower bound. Sorted a = [1, 2, 2, 2, 4], find first index with a[i] >= 2.

  1. Invariant: answer is in [lo, hi), start lo=0, hi=5.
  2. mid=2, a[2]=2 is already ≥ 2 → discard right half including? Keep mid as candidate: hi = mid.
  3. Narrow until lo == hi. Result index 1.

In code:

  • lo, hi = 0, len(a)
  • while lo < hi:
  • mid = (lo + hi) // 2
  • if a[mid] >= target:
  • hi = mid
  • else:
  • lo = mid + 1
  • return lo

3Recognise it

Kinds of problems (9)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Exact match

    Example. Find target in a sorted array, or return −1.

    How. Compare mid; discard the half that cannot contain target.

  • First / last position (lower and upper bound)

    Example. First and last index of target in a sorted array with duplicates.

    How. Lower bound: first index ≥ target. Upper bound: first > target. Same loop, different branch.

  • Insertion point

    Example. Index where target would be inserted to keep order.

    How. Same as lower bound: return lo when the loop ends.

  • Rotated sorted array

    Example. Sorted array rotated at an unknown pivot; find target.

    How. From mid, decide which half is sorted, then see which half can hold target.

  • Search a sorted 2-D matrix

    Example. Matrix rows are sorted and stitch into one increasing sequence.

    How. Binary search on the flattened index; map mid → (row, col).

  • Peak element

    Example. Find an index whose value is greater than its neighbours.

    How. Move toward the larger neighbour; a peak must exist in that direction.

  • Search on index parity (single element)

    Example. Every element appears twice except one; find the single (sorted pairs).

    How. Pairs sit on even-odd indices until the single breaks parity; binary search on that pattern.

  • Search for the start of a window (k closest)

    Example. k closest values to x in a sorted array.

    How. Binary search the leftmost start of a window of length k whose endpoints are closest to x.

  • Weighted random pick (prefix sums + search)

    Example. Pick an index with probability proportional to its weight.

    How. Build prefix sums of weights; draw r in [1, total] and lower-bound into the prefix.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Infinite loop

    Why it happens. When lo and hi stay adjacent, `lo = mid` or `hi = mid` can freeze the window.

    How it fails. lo = 0, hi = 1, mid = 0; setting lo = mid leaves lo == 0 forever.

    Fix. With while lo < hi, use lo = mid + 1 on the “too small” branch (or hi = mid, 1 on inclusive schemes). Bounds must shrink every step.

  • Inconsistent bounds

    Why it happens. Mixing [lo, hi] and [lo, hi) mid updates breaks the invariant.

    How it fails. hi = len(a)−1 but you still do hi = mid on “too big”, skipping the last index forever.

    Fix. Pick one convention and stick to it: either half-open [lo, hi) with hi = mid, or closed [lo, hi] with hi = mid, 1.

  • Wrong sorted half

    Why it happens. In a rotated array only one side of mid is sorted; searching the other side blindly misses the target.

    How it fails. a = [4,5,6,7,0,1,2], target = 0; discarding the right half because mid = 7 > 0 loses the only copy.

    Fix. Check which half is sorted (compare a[lo] and a[mid]), then ask whether target lies in that sorted range.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons