Binary search for a name in a hotel guest list
A hotel receptionist keeps the surnames of the 11 guests staying on one night in alphabetical order.
Adeyemi, Bakshi, Chen, Dlamini, Fernandes, Haddad, Ivanova, Kowalski, Mensah, Nakamura, Okafor
(a) Use the binary search algorithm to locate the name Nakamura in the list. You must make clear your choice of middle item and which part of the list you are rejecting at each stage. (3)
The receptionist also has a second list of the same 11 surnames, written in the order in which the guests arrived.
(b) Explain why the binary search algorithm cannot be used on this second list. (1)
- 1
(a) Number the names 1 to 11. There are 11 items, an odd number, so the middle item is in position : Haddad. Nakamura comes after Haddad alphabetically, so reject positions 1 to 6 (Adeyemi to Haddad). M1
- 2
The list is now positions 7 to 11: Ivanova, Kowalski, Mensah, Nakamura, Okafor. Five items, so the middle is the 3rd of them, position 9: Mensah. Nakamura comes after Mensah, so reject positions 7 to 9 (Ivanova to Mensah). A1
- 3
The list is now Nakamura, Okafor. Two items, an even number, so the middle is the nd of them, position 11: Okafor. Nakamura comes before Okafor, so reject Okafor. One item remains, position 10, and it is Nakamura: the name is found. A1
- 4
(b) Binary search works only on an ordered list: comparing the name with the middle item tells you which half cannot contain it. A list in order of arrival is not in alphabetical order, so the rejected half might contain the name. B1
Answer
(a) Middle items Haddad (reject Adeyemi to Haddad), Mensah (reject Ivanova to Mensah), Okafor (reject Okafor), then Nakamura: found in position 10. (b) The second list is not in alphabetical order, so rejecting half the list on a comparison is not valid.
Examiner tip
The usual loss is on the two-item list: the glossary rule gives the 2nd item (), Okafor, not Nakamura. Nakamura is not the glossary middle item, so stopping on it at that stage means the working does not follow the algorithm. Write down the rejected names each time, not just the middle item, and finish with an explicit "found".