Arrays and searching 0/120

Binary search · 1 of 3

Binary search technique

Find a value in a sorted array by halving the range, then find the first position where a yes-or-no question changes from NO to YES.

2,739 words · 13 min read

Part 1 of 7 Binary search

Search a sorted array by halving it

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.

To see how one comparison can rule out half of an array, take six sorted values and look for 14:

position   0   1   2   3   4   5value      3   8  11  14  20  27

Positions 0 to 5 have two middle positions, 2 and 3. Start at the lower one, position 2, which holds 11. That is less than 14. The array is sorted, so the values at positions 0 and 1 are smaller still, and none of the first three positions can hold 14. One comparison has ruled out all three, and 14 can only be at positions 3 to 5.

Now do the same with the positions that are left. The middle of 3 to 5 is position 4, which holds 20. That is more than 14, and every value after it is larger still, so positions 4 and 5 are out. Only position 3 remains, and it holds 14.

Each look at a middle value is called a probe. This search took three, at positions 2, 4 and 3.

A value that is missing shows up as a range with no positions left. Looking for 12 makes the same first two probes, because 12 is also more than 11 and less than 20. The third probe finds 14 at position 3, which is more than 12, so position 3 is ruled out as well. No position is left, which means 12 is not in the array.

On six values this saves little: a scan from the left finds 14 on its fourth comparison. The saving grows with the array, because every probe removes about half of whatever is left, however much that is.