Binary Search Scenario Generator
Binary search is four lines of code and famously hard to write correctly — the off-by-one errors live in the boundaries. This shows the whole trace: the range at every step, the midpoint it picked, the value it found there and which way it went. It also handles the harder case honestly: proving a value is absent costs exactly as much as finding one, because the range still has to shrink to nothing.
What this generator does
Builds a strictly increasing list and traces a binary search for a target that is either in it or deliberately between two entries. Every step records the range, the midpoint, the value found and the direction taken.
How to use this tool
- Choose how many sorted values and whether the target is present.
- Work through the search yourself, tracking low and high.
- Compare each step against the trace shown.
- Check the step count against the logarithmic bound.
Understanding the controls
- How many values
- Between 4 and 64 strictly increasing values.
- Search for a value that is present
- Off, the target sits between two entries — the case that exposes boundary bugs, since the search must end on an empty range.
- Seed
- Reproduces the same list and target exactly.
Common use cases
- Step-by-step binary search examples for teaching
- Test cases including the absent-value case that breaks implementations
- Showing why doubling the data adds only one comparison
- Debugging an off-by-one in a search implementation
- Reproducing the same list and target from a seed
How this generator works
The trace records low, high and midpoint before each comparison. The check re-runs the search from scratch and requires an identical trace, confirms the list is strictly increasing, requires the range to shrink at every step, and requires the total never to exceed the ceiling of the base-two logarithm.
Randomness and fairness
The values and the target are random; the trace follows deterministically. Seeded scenarios reproduce and are therefore explicitly not cryptographically secure. Unseeded, the browser's cryptographically secure generator builds the list.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Values are strictly increasing with no duplicates, so the find-the-first-occurrence variant is not exercised.
- Only the classic midpoint search; interpolation and exponential search are different algorithms.
- The list is generated rather than entered.
- No code is shown, only the trace.
- A traced search is not kept; seed it to walk the same list again.
Privacy and your data
The list and the trace are computed in your browser. Nothing about them or your seed is transmitted.
Related generators
- Sorting Algorithm Trace GeneratorAn array, an algorithm, and the state after every pass, with the comparison and move counts that distinguish the three.
- Binary Search Tree GeneratorAn insertion order and the tree it builds, with all three traversals, the height, and whether it came out balanced.
- Binary Heap GeneratorMin or max heaps built one insertion at a time, shown level by level, and drained to prove they sort.
- Complexity Comparison GeneratorTwo algorithms compared at every input size, with the crossover where better growth finally beats a large constant.