Practical Programming, 2nd Edition

Binary Search

Is there a faster way to find values than by doing a linear search? The answer is yes, we can do much better, provided the list is sorted. To understand how, think about finding a name in a phone book. You open the book in the middle, glance at a name on the page, and immediately know which half to look in next. After checking only two names, you have eliminated 3/4 of the numbers in the phone book. Even in a large city like Toronto, whose phone book has hundreds of thousands of entries, finding a name takes only a few steps.

This technique is called binary search, because each step divides the remaining data into two equal parts and discards one of the two halves. To figure out how fast it is, think about how big a list can ...