Next: Square and Other Roots Up: Divide and Conquer Previous: Fast Exponentiation

## Binary Search

Binary search is a fast algorithm for searching in a sorted array S of keys. To search for key q, we compare q to the middle key S[n/2]. If q appears before S[n/2], it must reside in the top half of our set; if not, it must reside in the bottom half of our set. By recursively repeating this process on the correct half, we find the key in a total of comparisons, a big win over the n/2 we expect with sequential search.

This much you probably know. What is important is to have a sense for just how fast binary search is. Twenty questions is a popular children's game, where one player selects a word, and the other repeatedly asks true/false questions in an attempt to identify the word. If the word remains unidentified after 20 questions, the first party wins; otherwise, the second player takes the honors. In fact, the second player always has a winning strategy, based on binary search. Given a printed dictionary, the player opens it in the middle, selects a word (say ``move''), and asks whether the unknown word is before ``move'' in alphabetical order. Since standard dictionaries contain 50,000 to 200,000 words, we can be certain that the process will always terminate within twenty questions.

Other interesting algorithms follow from simple variants of binary search. For example, suppose we have an array A consisting of a run of 0's, followed by an unbounded run of 1's, and would like to identify the exact point of transition between them. Binary search on the array would provide the transition point in tests, if we had a bound n on the number of elements in the array. In the absence of such a bound, we can test repeatedly at larger intervals (A[1], A[2], A[4], A[8], A[16], ) until we find a first non-zero value.     Now we have a window containing the target and can proceed with binary search. This one-sided binary search finds the transition point p using at most comparisons, regardless of how large the array actally is. One-sided binary search is most useful whenever we are looking for a key that probably lies close to our current position.

Next: Square and Other Roots Up: Divide and Conquer Previous: Fast Exponentiation

Algorithms
Mon Jun 2 23:33:50 EDT 1997