Algorithm Lab / Simulation

Watch binary search narrow the answer

Change the sorted input, choose a target and inspect every comparison. No animation hides the invariant.

You will learn to

  • Trace low, high and midpoint
  • Explain logarithmic search
  • Recognize the sorted-input prerequisite

Before you start

Ordered numbers and indexes

The invariant

Binary search maintains a candidate interval. If the target exists, it remains inside that interval. A smaller middle value eliminates the left half, including the middle. A larger middle value eliminates the right half. The +1 and -1 updates matter: without them a two-element interval may never shrink.

Cost and tradeoffs

Each comparison removes roughly half the remaining candidates. Search takes O(log n) comparisons and O(1) auxiliary space. Sorting first may cost more than a linear search for a one-off task. This lab requires sorted input rather than silently changing your problem.

Experiments

Find the first item, the last item and a missing item. Try one element and repeated values. With duplicates, this implementation returns one matching index, not necessarily the first. Record which interval disappears after each step.

Try it yourself

Enable JavaScript for this interactive activity. You can read all lesson explanations above without it.

Continue exploring