Binary Search
Finding elements in sorted data by halving the search space.
Free theory articleFinding elements in sorted data by halving the search space.
Concept & interpretation
Binary search saves comparisons because a sorted array lets one comparison rule out an entire interval. Trace an eight-element example by hand, then select the corresponding position in Riano's generated array. The numbers on screen may change; the reasoning about sorted positions stays the same.
Repeat the index trace with actual controls
Open Binary Search. It generates sorted, distinct values rather than accepting a custom array.
- Set Array Size to 8 and click “Randomize” to build a new eight-element array. Record its values if you want to replay the same reasoning on paper.
- Click the sixth array cell, at index 5. Clicking a cell starts a search for that cell's actual value. Predict midpoint indices 3 and 5 and two comparisons.
- Try the first cell. The midpoint indices are 3, 1 and 0; explain the two leftward updates before the match.
- Use the Search control or click other cells and compare the candidate interval with the eliminated cells. A faster speed shortens the animation delays, not the comparison count.
Do not expect your random values to match the paper array. The missing-target table is also a paper exercise: the UI primarily selects targets from existing cells and does not expose a free-form target field.