Halve and find
Answers are for parents and teachers.
1
Put these in ascending order: 205, 18, 96, 7, 150. Then put the words kiwi, date, plum, cherry, banana in descending alphabetical order.
Numbers: 7, 18, 96, 150, 205. Words in descending order: plum, kiwi, date, cherry, banana.
2
The sorted list is 12, 20, 28, 35, 41, 50, 62, 70, 85. Use a binary search to find 62. Write the centre item at each check and the number of comparisons.
Check 1: centre 41; 62 > 41, so discard 41 and the left side, leaving 50 62 70 85. Check 2: four items, so take the left middle one, 62; found. It takes 2 comparisons.
3
Use the same list to look for 30. Is it found? Write each centre item and the result.
Check 1: centre 41; 30 < 41, leaving 12 20 28 35. Check 2: centre 20; 30 > 20, leaving 28 35. Check 3: centre 28; 30 > 28, leaving 35. Check 4: centre 35; 30 < 35, and nothing is left. The result is not found, after 4 comparisons.
4
A friend says: ‘I will use a binary search on my list 14, 3, 9, 22, 6, because it is the fastest.’ Explain what your friend must do first, and why.
The friend must sort the list first (3, 6, 9, 14, 22), because a binary search only works on data that is in order.
5
Explain in your own words why the search is called a binary search. Give an example of two choices at each step.
Binary means two. At every step the data is split into two halves, and one half is kept and the other is discarded. The two choices are: the target is smaller than the centre item, so keep the left side, or the target is larger, so keep the right side.