Finding one item in a sorted list by halving

Prefix sums relied on the data standing in a row, so you could add up any stretch. Sorted data has another useful property: order. When a list is in order, you don't need to look at everything to find one item. One check removes half of the list.

You have a million log lines, stored in order of time. Someone asks for the entry at 14:32:07. You could read from the top, line by line, until you reach it. On a million lines that is up to a million reads for one search, and searches happen all the time.

When the data is already sorted, any item out of a million is found in about 20 checks instead of a million.

Take the sorted test list [1, 3, 5, 7, 9, 11] and look for 7. Look at a number in the middle: 5. It is smaller than 7. The list is sorted, so 1 and 3, which stand to the left of 5, are smaller still. One look removed three numbers. Only 7, 9 and 11 are left. Look at their middle: 9. It is bigger than 7, so 9 and 11 are out. Only 7 is left, and it is the one. Three looks instead of six.

The gain grows with the list. Each look removes about half of what is left. A million sorted log lines shrink to 500,000, then 250,000, then 125,000, and so on. After 19 looks one line is left, and the 20th look checks it. This works only because the list is in order. In an unordered list, a 5 that is smaller than 7 would tell you nothing about its neighbours.

Keep two markers, lo and hi. They mark the part of the array where the target may still be. At the start that is the whole array. Look at the element in the middle between them.

There are three outcomes. If the middle element equals the target, the search is over. If it is smaller than the target, the target can only be to its right, so move lo past the middle. If it is bigger, the target is to its left, so move hi before the middle. Each check removes half of what was left.

One rule protects you from an endless loop: set lo to mid + 1 and hi to mid - 1, and never set them to mid itself. If a marker lands on mid again, the range stops shrinking, and the loop runs forever. Stop when lo becomes bigger than hi. That means the target is not in the array, so return -1.

Trace it on [1, 3, 5, 7, 9, 11], looking for 7.

• Start: lo = 0, hi = 5. The middle is index 2, which holds 5. That is smaller than 7, so lo = 3.
• Now lo = 3, hi = 5. The middle is index 4, which holds 9. That is bigger than 7, so hi = 3.
• Now lo = 3, hi = 3. The middle is index 3, which holds 7. A match.

Found at index 3: three checks instead of six.

Time is O(log n): each step halves what is left. A million items need about 20 steps, and a billion about 30. That is the almost flat curve from lesson 09: it barely rises as the data grows.

Memory is O(1): three index variables and nothing that grows with the array. There is one condition: the input must already be sorted. If it is not, sorting costs O(n log n). That pays off only when there will be many searches.

Finding a record in sorted logs and time-series stores. A lookup in a B-tree (the structure behind database indexes) is binary search adapted to work with a disk. Finding a version in a sorted list of releases. The lower_bound and upper_bound functions in standard libraries. The git bisect command finds the commit where a bug appeared: it halves the range of commits every time. It is the same idea, applied to a history of versions in place of an array.