Binary Search

A sequential search works on any list at all. But if the data happens to be SORTED, we can do far better.

The binary search algorithm starts at the middle of a sorted data set of numbers and eliminates half of the data. This process repeats until the desired value is found or all elements have been eliminated.

The rule has two steps:

1. Look at the middle of the array. If the target is found, we are done. Otherwise, if the target is greater than that value, we can eliminate the left half of the array. And if the target is less than the value, eliminate the right half.
2. Repeat with the left or right half of the array accordingly.

Each probe looks at one element, and if that element is not the target it lets us throw away half of what is left. Take a list of 100 items: six HALVINGS cut it down to a single candidate. But that survivor has not been looked at yet, and looking at it is what tells us whether the target is there at all.

So the number of elements actually examined is one more than the number of halvings: seven for a hundred items, which is what the table's binary column shows.

Suppose we have a list of size n. In the worst case, sequential search needs n comparisons, and binary search needs approximately log base 2 of n.