Halve the search space

Because the array is sorted, comparing the target to just one middle element tells you conclusively which half it could still be in — everything on the other side is guaranteed too small or too large, so it can be thrown away without ever being examined. Repeating that single trick shrinks the search space in half every time, so finding a value among n cells takes only about log2(n) probes. Reach for it whenever the data is sorted (or monotonic) and you need a fast lookup or boundary.

Details

Animated on: Find 23 in the sorted array [4, 9, 15, 23, 28, 37, 50]

Problem:Binary SearchEasy

Pattern:Binary Search on Sorted Data

Binary Search

step 1 / 11

[0]

[1]

[2]

[3]

[4]

[5]

[6]

Sorted array, target 23. Sorted order is the superpower: one look at the middle tells us which half can be thrown away.

Pseudocode

1FUNCTION lowerBoundSearch(arr, target):
2  lo = 0, hi = the length of arr - 1
3  WHILE lo < hi:
4    mid = (lo + hi) / 2, rounded down
5    IF arr[mid] < target:  lo = mid + 1
6    ELSE:  hi = mid
7  END WHILE
8  RETURN lo if arr[lo] === target, otherwise -1
9END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 11 steps

Sorted array, target 23. Sorted order is the superpower: one look at the middle tells us which half can be thrown away.
lo and hi fence the search space — every index between them is still a candidate. At the start that's the whole array: lo=0, hi=6.
Loop test: lo(0) < hi(6), so more than one candidate remains — keep halving.
mid = (0+6)/2 = 3. Probing the middle splits the candidates evenly, so each comparison can kill half of them.
arr[3]=23 is NOT < 23, so the target can't be right of mid. hi=mid keeps index 3 alive (we pin the FIRST match) and discards 4-6 in one move.
Still lo < hi (0 < 3). New middle of the survivors: mid=(0+3)/2=1, value 9.
9 < 23 — mid is too small, so the target must sit RIGHT of it. lo=mid+1=2; indices 0-1 are discarded.
Two candidates left (lo=2 < hi=3). mid=(2+3)/2 rounds down to 2, value 15.
15 < 23 — still too small, the target lies right of mid. lo=mid+1=3. Only index 3 survives.
lo and hi have converged on index 3 — the search space is one cell, so the loop exits. If 23 exists anywhere, it must be here.
Verify: arr[3]=23 — target found at index 3. Three probes instead of scanning seven cells: that's the O(log n) payoff.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Binary Search in the editor All Binary Search problems Back to roadmap