- In the searching problem, assume that the names in the phone book are sorted
in alphabetical order, written
N1 < N2 < ,..., < Nn
- 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?
WORK THROUGH THE DEMONSTRATION
CS1104 Main Page
Last Updated 01/05/2000
©J.A.N. Lee, 2000