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.

Computer Science & Information Technology

You might also like to view...

A recursive module is similar to a(n) __________ in that it must have some way to control the number of times it repeats.

a. loop structure b. case structure c. decision structure d. library

Computer Science & Information Technology

Use the _______ attribute on a video element to display user controls for the video player.

a. poster b. player c. controls d. image

Computer Science & Information Technology

What is the result when the two’s complement of a number is added to itself?

What will be an ideal response?

Computer Science & Information Technology

Text that is typed in a cell that extends into the next cell only displays if the two cells are merged

Indicate whether the statement is true or false

Computer Science & Information Technology