Binary search is an extremely important algorithm, but it turns out that it is subtle to get the implementation just right. (It has been observed that although the first binary search was published in 1946, the first published binary search without bugs did not appear until 1962.) The basic idea is the same as the algorithm we all tend to use when we're asked to guess a number between 1 and 100: ``Is it between 1 and 50? Yes? Okay, is it between 25 and 50? No? Okay, is it between 1 and 12? ... '' (Don't worry if you can't follow all of the details of the algorithm or the code on page 58, but do remember to be extremely careful if you're ever asked to write a binary search routine.)
Read sequentially: prev next up top
This page by Steve Summit // Copyright 1995, 1996 // mail feedback