Binary Search

A binary search finds an item in a sorted list by repeatedly examining the middle item of the part still being searched. The list must be sorted first, or the search may fail.

How it works

The search area is tracked with a lower bound, an upper bound and a middle position. The middle position is found by integer division of the bounds, which rounds down. If the section has an even number of items, this gives the lower central position.

The middle item is compared with the target. If they match, the search stops and reports the item as found. If the target is smaller or earlier, the middle item and everything after it are discarded, and the upper bound becomes the middle position minus one. If the target is larger or later, the middle item and everything before it are discarded, and the lower bound becomes the middle position plus one. The search repeats on the remaining half.

Worked example

Search for bus route 67 in the sorted route numbers 4, 9, 15, 22, 31, 40, 52, 67, 73, 88, 94, 100.

So route 67 was found in four comparisons.

When it is not found

If the lower bound becomes greater than the upper bound, no items remain, so the item is not in the list. For example, searching for route 60 compares 40, then 73, then 52, then 67; after 67, the lower bound 7 is greater than the upper bound 6.

Binary search is faster than linear search on a large sorted list because each comparison discards half the remaining items. It is more complex to write than linear search and needs sorted data: on an unsorted list, discarding half could throw away the target.