Say you have a sorted array of a million numbers and want to know whether 7,412 is one of them. Checking the numbers one by one from the left can take a million comparisons. Binary search finds a value in a sorted array by comparing it with the middle element, which rules out half of the array, and repeating the same step on the half that is left. For a million numbers it never has to look at more than 20 of them.
The binary search loop
In code, the search keeps two variables, left and right: the first and the last position where the target could still be. At the start they are the two ends of the array, positions 0 and . As long as the range from left to right holds at least one position, the loop probes the middle one, mid, and compares its value with the target:
- If the value at
midequals the target, the search is over: the target is atmid. - If the value is less than the target,
midand every position before it are ruled out, soleftmoves tomid + 1. - If the value is greater than the target,
midand every position after it are ruled out, sorightmoves tomid - 1.
Every pass either ends the search or takes mid out of the range, so the range gets shorter each time and the loop has to end. The loop only removes positions whose values are too small or too large to be the target, so if left passes right and the range is empty, the target is not in the array.
How many probes can a search take? A probe leaves at most half of the positions that were in the range, because neither side of mid holds more than half of them. A million positions become at most 500,000 after one probe, 250,000 after two, and fewer than two after 19. So at most one position is left for the 20th probe, and a million values never take more than 20 probes:
Halve the candidate range with binary search
In this stepper you make the decision at each probe. The purple cell is mid, the line under the cells gives its answer, and you choose which side of mid to keep searching. A wrong choice is explained and not applied.