Reaktiv Workbook

Binary search: halve the possibilities

A sorted list lets us discard half of the candidates after every comparison. The outlined number is the one being inspected; faded numbers are already excluded.

Interactive widget (SearchStepper)Try it in the web app →

You are looking at step 1 of 3 — the stepper writes the input cell search_step, so the step is saved with the workbook.

Searching for 23: found in 3 comparisons. A list of 9 numbers never needs more than 4 comparisons (\lfloor \log_2 n \rfloor + 1); a linear scan may need all 9.

Predict before clicking

Is the target larger or smaller than the outlined number? Which half can you safely discard? Then change the list or the target in the cells and step through again.