Suppose you needed to look up a number in your local phone book. Roughly, what is the population of your city? How many checks would be required, in the worst case, to find the phone number using sequential search? How many checks would be required, in the worst case, to find the phone number using binary search?

What will be an ideal response?

Student answers will depend upon local population. For sequential search: In the best case, the name will appear first in the book, requiring only 1 inspection. In the worst case, the name will appear last in the book, requiring all entries to be inspected. For binary search: In the best case, the name will appear in the exact middle of the book, requiring only 1 inspection. There are many worst case positions, including the first and last positions in the book, requiring log2 N inspections, where N is the number of entries in the book.