Practise Linear and binary search. 13 exam-style questions plus unlimited generated ones on this subtopic, at up to four difficulty levels, with full mark schemes and a progress tracker. Free, no account needed.
Cover the answers and test yourself. The app has these as flashcards that come back just before you'd forget them.
State one advantage of a linear search compared with a binary search.
It works on a list that is not sorted.
State the condition that the list must meet for a binary search to work.
The list must be sorted (in order).
Sample questions
Written for this site in the style of Edexcel exam questions. They are not taken from real past papers.
Question 1Easy4 marks
A linear search is used to find a name in a list of names.
(a) Describe how a linear search works.[2]
(b) State one advantage of a linear search compared with a binary search.[1]
(c) The list contains 50 names. State the maximum number of names that a linear search would need to check.[1]
Show the answer and mark scheme
(a)Answer: It starts at the first item and checks each item in turn until the item is found or the end of the list is reached.
starts at the first item and checks each item in turn / one after another
until the item is found or the end of the list is reached
(b)Answer: It works on a list that is not sorted.
it works on unsorted lists / it is simpler to program
(c)Answer: 50
50
Question 2Medium5 marks
(a) Identify the algorithm that uses a divide and conquer approach.[1]
Linear search
Binary search
Bubble sort
Adding up the items in an array
(b) Explain why binary search is described as a divide and conquer algorithm.[2]
(c) Explain why binary search can only be used on a list that is in order.[2]
Show the answer and mark scheme
(a)Answer: Binary search
(b)Answer: Comparing with the middle item splits the list in two and discards one half, so the search keeps shrinking the problem.
each comparison with the middle item splits the list that is still being searched into two halves
one half is discarded, so the problem is repeatedly made smaller until the item is found or no items are left
(c)Answer: It discards a half after comparing with the middle item, which is only safe if the list is sorted.
the algorithm decides which half to discard by comparing the target with the middle item
this only works if every item before the middle is smaller and every item after it is larger (the list is sorted), otherwise the target could be in the discarded half
Question 3Hard9 marks
This function should use a binary search to return True if target is in the sorted list items. Four lines are incomplete.
01 def binarySearch(items, target):
02 low = 0
03 high = ______
04 found = False
05 while low <= high and not found:
06 mid = ______
07 if items[mid] == target:
08 found = True
09 elif items[mid] < target:
10 ______
11 else:
12 ______
13 return found
(a) Write the missing code for lines 03, 06, 10 and 12.[4]
(b) Explain why line 10 uses mid + 1 rather than mid.[2]
(c) The function is called with a list that is not sorted: binarySearch([9, 2, 7, 4, 5], 2). State the value returned.[1]
(d) Explain why this value is returned, even though 2 is in the list.[2]
(b)Answer: The item at mid has already been compared with the target (and is smaller than it), so it can be left out of the part still to be searched. Using mid could leave low unchanged, for example when low and high are next to each other, so the loop might never end.
the item at index mid has already been checked / is smaller than the target, so it does not need to be searched again
using mid could leave low unchanged (e.g. when low and high are next to each other), so the loop might never end
(c)Answer:False
False
(d)Answer: The search checks 7 first. 7 is bigger than 2, so the items from index 2 onwards are discarded. It then checks 9, which is also bigger than 2, so the search ends before 2 (at index 1) is checked.
the list is not sorted, so the search checks 7 (then 9), which is bigger than 2, and discards the part of the list to its right
the search ends without checking index 1, where 2 is stored