- In the searching problem, assume that the names in the phone book are sorted
in alphabetical order, written

*N*_{1}<*N*_{2}< ,..., <*N*_{n} - This is, of course the situation with a "normal" phone book.
- We know, intuitively, that this helps us with searching for
*NAME*. (It does not help us with searching for a phone number.) - The improved algorithm is the very important
**binary search**:- Find the item at the center of the search domain
- Is it the item sought? If so collect any necessary data and then exit.
- If not, determine in which half of the domain the item sought is to be found.
- Use this half as the new domain
- Start again

**How many items can be searched in four steps?
How many items can be searched with m comparisons?
Does it matter if the length of the list is not a power of 2?**

CS1104 Main Page

Last Updated 01/05/2000

©J.A.N. Lee, 2000