# Recall that Chapter 8 described the binary search algorithm for finding a particular entry in an ordered

## Question:

Recall that Chapter 8 described the binary search algorithm for finding a particular entry in an ordered list. The idea behind binary search is to begin looking in the exact center of the list. If the desired entry comes before the middle entry in the list's organizational scheme, then you can eliminate all entries beyond the middle and repeat the process on the remaining half of the list. Similarly, if the desired entry comes after the middle entry, you can eliminate all entries before the middle and repeat the process on the remaining half. Every time you perform a comparison, you reduce the size of the list by one-half. Eventually, you either locate the desired entry or determine that it isn't in the list.

Now that you understand how the binary search algorithm works, you can use your modified countdown.html page to determine how many checks are needed to locate an item in a particular ordered list. If you enter a list size in the text box, the sequence of numbers displayed in the text area will represent the remaining size of the list to be searched after each successive inspection. Thus, the number of values in the text area will be one more than the number of checks required to find an entry in the worse case. To more easily identify this necessary number of checks, add a counter to your countdown.html page that records how many times the value is halved before reaching 0. When the countdown completes, the browser should display the counter's value below the sequence in the text area. For example, if the initial value of count were 10, your page would produce the following output:

10

5

2

1

0

number of halvings = 4

Use your modified countdown.html page to determine how many times the following numbers must be halved (and, if necessary, rounded down) before reaching 0:

32

64

128

6000

308000000

6800000000

The last three numbers in this exercise approximate the size of a small university's student body, the U.S. population, and the world population, respectively. Thus, the results you obtained represent the maximum number of binary search comparisons required to find an entry in listings of these populations?

## Step by Step Answer:

**Related Book For**