BEGINNER · 8 MIN · FREE LESSON

Binary search

Cut the problem in half.

Size 8

default
? comparing
↔ moving
✓ visited
Q queued
✓ done

Find 6 in this sorted array.

Code language

Speed

1 / 7

Live variables

target: 6
low: 0
high: 5

Operation counters

comparisons: 0
swaps: 0
reads: 0
writes: 0

Complexity · O(log n)

best: O(1)
average: O(log n)
worst: O(log n)
space: O(1)

Each comparison removes at least half of the remaining sorted search interval.

n=8

n=16

n=32

n=64

Measured reads + comparisons, seed 42. Plotted sample sizes respect each lesson’s explicit input limits.

Keyboard: Space play/pause · ←/→ step · R restart · 1–5 speed. Reduced motion disables transitions.

Binary search

Hook

Like opening a dictionary in the middle, each comparison rules out half the remaining pages.

Watch

Use the player above to run, pause, scrub, or step backwards through a deterministic trace.

How it works

Start with sorted values.
Compare the middle value to the target.
Keep only the half that could contain the target.
Stop at a match or an empty interval.

Try it

Switch to Try mode and predict each operation before revealing its result.

Complexity

Every comparison halves the remaining interval. Use best, average and worst presets to compare measured counters. The chart plots actual reads and comparisons for n = 8, 16, 32 and 64.

Code

Choose JavaScript, Python, Java or C++ in the synchronized code panel.

When to use

Searching sorted random-access data.

Interview pitfalls

An unsorted input breaks the invariant; off-by-one boundaries cause missed values.

Quiz

Complete the three questions below, then use the module navigation to choose your next lesson.

MAKE IT STICK

Quick knowledge check

Progress saves on this device and merges with your account after sign-in.

Your notebook

Private lesson notes

0 / 5000 · Saved on this device; synced when signed in.

Loading interactive lesson…

Next: Binary search on answer →