Chapter 7.3, Problem 59PS

Solution

i.

To identify: The rule for the number of items remaining after the nth pass through an ordered list of 1024 items.

A binary search technique used on a computer involves jumping to the middle of an ordered list of data (such as an alphabetical list of names) and deciding whether the item being searched for is there. If not, the computer decides whether the item comes before or after the middle. Half of the list is ignored on the next pass, and the computer jumps to the middle of the remaining list. This is repeated until the item is found.

The required rule is $\frac{1024}{2^n}$ and value of $n=10$ .

Given information:

The given terms are $a_1=1024\text{and}r=\frac{1}{2}$ .

Explanation:

Consider the given sequence.

It is given that $a_1=1024\text{and}r=\frac{1}{2}$ .

The general formula for a geometric sequence is $a_n=a_1\cdot r^{n-1}$ .

After the 1^st pass item will be left to be searched $\frac{1024}{2}=512$

After the $2_{nd}$ pass item will be left to be searched $\frac{512}{2}=256$

But $\frac{512}{2}=\frac{1024}{2^2}$

After the $3_{nd}$ pass item will be left to be searched $\frac{256}{2}=128$

But $\frac{256}{2}=\frac{1024}{2^3}$

As you can see after the nth path, $\frac{1024}{2^n}$ item will be left to be searched

ii.

To calculate: In the worst case, the item to be found is the only one left in the list after n passes through the list. What is the worst-case value of n for a binary search of a list with 1024 items? Explain

The total number games played $62$ .

Explanation:

Consider the given sequence.

It is that from above calculation $a_n=\frac{1024}{2^n}$

In the worst case, the item to be found is the only one left in the list after $n$ passes through the list thus the worst case is $a_n=1$ .

  $\begin{array}{l}{a}_n=\frac{1024}{2^n}\\ 1=\frac{1024}{2^n}\\ 1=\frac{2^{10}}{2^n}\\ 2^n=2^{10}\\ n=10\end{array}$

That the worst case value of $n$ for a binary search of a list with $1024$ is $n=10$