Question 1
2 marksHannah has this list of numbers:
12, 5, 30, 8, 19, 2, 27
She wants to find the number 19.
Explain why a binary search could not be used on this list as it is, and state the searching algorithm she could use instead.
Model answer
A binary search only works on a sorted list, and this list is not in order, so the search could discard the half that contains 19. She could use a linear search instead.
Explanation
A binary search decides which half to discard by assuming everything before the middle item is smaller and everything after it is larger; that is only true in a sorted list. A linear search checks every item in turn, so it works on unsorted data. Hannah could also sort the list first and then use a binary search.
Mark scheme
-
1 mark
the list is not sorted / not in order (and a binary search needs sorted data, otherwise it may discard the half containing 19)
Do not accept 'it has an odd number of items' or 'the list is too short'.
-
1 mark
linear search
accept sequential / serial search