D1 January 2007 Q1
1. Use the binary search algorithm to try to locate the name NIGEL in the following alphabetical list. Clearly indicate how you chose your pivots and which part of the list is being rejected at each stage. (4)
1. Bhavika
2. Clive
3. Elizabeth
4. John
5. Mark
6. Nicky
7. Preety
8. Steve
9. Trevor
10. Verity
| Scheme | Marks |
|---|---|
| \(\left[\dfrac{1+10}{2}\right] = \underline{6}\) Nicky – reject top of list. | M1 |
| \(\left[\dfrac{7+10}{2}\right] = \underline{9}\) Trevor – reject bottom of list | A1 |
| \(\left[\dfrac{7+8}{2}\right] = \underline{8}\) Steve – reject bottom of list | A1 |
| \([7] = \underline{7}\) Preety – reject Nigel not in list. | A1 |
| (4 marks) |