Binary Search
Interactive lab
Try it: Binary Search
How binary search finds a value in a sorted list by checking the middle and throwing away the half that cannot contain it.
How it works
- Start with the whole sorted list as the search interval (lo to hi).
- Look at the middle value.
- If it is the target, stop. If the target is larger, discard the left half; if smaller, discard the right half.
- Repeat until the target is found or the interval is empty (not found).
Default run (7 steps): Search for 17 in [2, 5, 9, 13, 17, 21, 30]. The whole array is the search interval: lo = 0, hi = 6. … 17 = 17 — found at index 4 after 3 comparisons.
Educational simulation
Loading the simulation…