Binary Search Algorithm

2. In a television gameshow the names of 100 celebrities are listed in alphabetical order. A name is chosen at random from the list and a contestant has to guess which celebrity has been chosen. If the contestant is not correct, the host indicates whether the chosen name comes before or after the contestant's answer in the list and the contestant makes another guess. Each contestant knows all the names on the list and has to find the chosen name in as few guesses as possible.

1. Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
2. A large database with up to one million ordered entries is to be interrogated in the same way using appropriate software. Find the maximum number of interrogations that would be required for the software to find a particular entry and explain your answer.

1. (a) Use the binary search algorithm to locate the name PENICUIK in the following list.

\begin{displayquote} ANKERDINE CULROSS DUNOON ELGIN FORFAR FORT WILLIAM HADDINGTON KINCARDINE LARGS MALLAIG MONTROSE PENICUIK ST. ANDREWS THURSO
(b) Use the same algorithm to attempt to locate PENDINE.
(c) Explain the purpose of the mid-point in dividing up the ordered list when using this algorithm. \end{displayquote}

1. Use the binary search algorithm to try to locate the word "Parallelogram" in the following alphabetical list. Clearly indicate how you choose your pivots and which part of the list you are rejecting at each stage.

Arc Centre Chord Circle Circumference Diameter Radius Sector Segment Tangent

1.
\(\begin{array} { l l l l l l l l l l } 17 & 9 & 15 & 8 & 20 & 13 & 28 & 4 & 12 & 5 \end{array}\)

3. \(\begin{array} { l l l l l l l l l l l } 1.8 & 1.4 & 2.6 & 1.6 & 2.8 & 0.9 & 3.1 & 0.8 & 1.2 & 2.4 & 0.6 \end{array}\)