OCR GCSE Computer Science (J277) · Algorithms and programming (Paper 2) › Algorithms › Searching and sorting algorithms
Practise Linear and binary search. 11 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.
Written for this site in the style of OCR exam questions. They are not taken from real past papers.
Question 1Easy4 marks
(a) Which search algorithm can only be used when the data is sorted? Tick (✓) one box.[1]
Binary search
Linear search
Both linear search and binary search
Neither linear search nor binary search
(b) Describe how a linear search finds an item in a list.[2]
(c) Give one advantage of a linear search compared with a binary search.[1]
Show the answer and mark scheme
(a)Answer: Binary search
(b)
checks / compares each item in turn, starting with the first item
until the item is found / until the end of the list is reached (the item is not in the list)
(c)
the data does not need to be sorted
it is simpler to code / understand
it can be quicker for a very small list / when the item is near the start of the list
Question 2Medium5 marks
A mobile phone stores 2000 contacts in alphabetical order of name.
(a) Explain why a binary search would usually find a contact more quickly than a linear search.[2]
(b) State the maximum number of names a linear search would check when looking for a contact.[1]
(c) The phone also keeps a list of the 20 most recent calls, stored in the order in which the calls were made. Explain why a linear search would be used to find a name in this list.[2]
Show the answer and mark scheme
(a)
each comparison in a binary search discards / halves the part of the list left to search
so far fewer comparisons are needed (at most 11 for 2000 items, compared with up to 2000 for a linear search)
(b)Answer: 2000
2000
(c)
the list is not sorted by name, and a binary search needs sorted data
the list is short, so a linear search is fast enough / sorting it first would take extra time
Question 3Hard7 marks
A library catalogue contains 1000 book titles in alphabetical order.
(a) State the maximum number of titles a linear search would need to check.[1]
(b) Each comparison in a binary search halves the number of titles still to be searched. Calculate the maximum number of comparisons a binary search would need. Show your working.[2]
(c) The number of titles doubles to 2000. Describe the effect on the maximum number of comparisons needed by each type of search.[2]
(d) New titles are added to the catalogue every day. Explain one disadvantage of using a binary search for this catalogue.[2]
Show the answer and mark scheme
(a)Answer: 1000
1000
(b)Answer: 10 (210 = 1024, which is at least 1000)