Binary Search
Finding elements in sorted data by halving the search space.
By Riano · Published · Updated · Report a correction
Binary search: justify each half you discard
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.
Keep a precise candidate interval
Use zero-based indices and an inclusive interval [low, high]. If the target is present, it must remain inside that interval. Choose mid = low + floor((high − low)/2). If the midpoint value is too small, all values through mid are too small, so set low = mid + 1. If it is too large, set high = mid − 1.
Equality ends a successful search. If low becomes greater than high, no candidate remains. Moving past mid is essential: keeping an already rejected midpoint can prevent progress, especially when only one or two elements remain.
Worked example: find 31 in two comparisons
On paper, take the sorted array [3, 7, 12, 18, 26, 31, 44, 59] and target 31. This array is an illustration, not a promise that Randomize produces those exact numbers.
- Start at low = 0 and high = 7. The midpoint is 3, where the value is 18.
- Since 18 is less than 31, discard indices 0 through 3. The new interval is [4, 7].
- The midpoint is now 5, where the value is 31. The search succeeds after two comparisons at index 5, the sixth position.
| Comparison | Interval | Midpoint value | Next action |
|---|---|---|---|
| 1 | [0, 7] | 18 at index 3 | low = 4 |
| 2 | [4, 7] | 31 at index 5 | high = 4 |
| 3 | [4, 4] | 26 at index 4 | low = 5; interval is empty |
The unsuccessful search proves absence by exhausting the candidate interval. Merely not matching the first midpoint would not justify that conclusion.
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.
Sorted order is the permission to discard
Binary search can miss a present value in an unsorted array because the comparison no longer justifies removing a half. The module supplies sorted unique integers, so it does not test unsorted inputs, duplicate-handling policies or comparator consistency.
At most floor(log2 N) + 1 midpoint comparisons are needed for a nonempty array with this search convention. For N = 8 the worst case is 4, although the chosen sixth cell takes only 2. This bound counts comparisons after the data is sorted. Sorting an unsorted collection has its own cost, and array access is assumed constant-time. A sorted linked list does not provide the same access model.
Try a small interval by hand
For [4, 9], search for 9. With low = 0 and high = 1, the first midpoint is 0. The update low = 1 leaves the second element for the next comparison. Explain why an update low = mid could get stuck in the same situation.
Source for the sorted-array search model
MIT OpenCourseWare, Introduction to Algorithms, Lecture 3: Sorting describes the logarithmic search bound for sorted arrays. The two traces here use Riano's inclusive low/high convention and are independently worked examples, not copied program output.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Binary Search module.
Try Binary Search on Riano →