Level:
Correct: 0
Incorrect: 0
Marks: 0/0
Exam Practice
Course:
Topics:
OCR GCSE Computer Science (Paper 2) Smart practice A mixed round aimed at your weak spots
Unit 1
Algorithms
Unit 2
Programming fundamentals
Unit 3
Producing robust programs
Unit 4
Boolean logic
Unit 5
Programming languages and IDEs
Unit 6
Practical programming (Section B)
Avg
score:
–
Topics
done:
0/31

Linear search and binary search

Practise 32 exam-style questions on Linear search and binary search for OCR GCSE Computer Science (Paper 2). Write your answer as you would in the exam and get it marked in seconds against the mark scheme, point by point, with the Study Helper on hand if you get stuck.

  • 32 questions
  • 1–6 marks each
  • Instant marking
  • No sign-up needed
20 questions, marked as you go

Sample questions with model answers

Here are 4 of the questions in this topic, each with a model answer, an explanation of why it earns the marks and the mark scheme an examiner would use.

Question 1

2 marks

Hannah 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. 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'.

  2. 1 mark

    linear search

    accept sequential / serial search

Question 2

3 marks

Describe how a linear search finds a target item in a list.

Model answer

A linear search starts with the first item in the list and compares it with the target. If they match, the item has been found and the search stops. If not, it moves on to the next item and compares that. This repeats until the item is found or the end of the list is reached, in which case the item is not in the list.

Explanation

A linear search checks the items one at a time, in order, starting from the first. It does not need the list to be sorted, which is its main advantage. A common mistake is to describe it vaguely ('it searches the list'): say where it starts, what it compares and when it stops.

Mark scheme
  1. 1 mark

    starts at the first item in the list / index 0

    max 3. One idea, one mark. Do not credit any description of a binary search (e.g. 'looks at the middle item'). 'It searches through the list' on its own earns nothing.

  2. 1 mark

    compares the current item with the target / checks whether the item is the one being searched for

  3. 1 mark

    if they match, the item has been found (and the search stops / its position is output)

  4. 1 mark

    if they do not match, moves on to the next item (and repeats the comparison)

    allow 'checks each item in turn / one at a time, in order'

  5. 1 mark

    repeats until the item is found or the end of the list is reached (so the item is not in the list)

Question 3

4 marks

A list holds these names in alphabetical order:

Aled, Bethan, Carys, Dafydd, Eleri, Ffion, Gethin, Huw, Iwan

A binary search is used to look for the name "Gareth". The first name is at index 0, and the middle item is at index (first + last) DIV 2, where first and last are the indexes of the first and last names still being searched.

Give the names that are compared with "Gareth", in order, and explain how the algorithm finds out that "Gareth" is not in the list.

Model answer

first = 0, last = 8, mid = 4: Eleri. Gareth comes after Eleri, so first = 5.
first = 5, last = 8, mid = 6: Gethin. Gareth comes before Gethin, so last = 5.
first = 5, last = 5, mid = 5: Ffion. Gareth comes after Ffion, so first = 6.
Now first (6) is greater than last (5), so there are no names left to search and Gareth is not in the list.

Names compared: Eleri, Gethin, Ffion

Explanation

Names are compared alphabetically, letter by letter: Gareth comes before Gethin because 'a' comes before 'e'. A binary search knows an item is missing when the part of the list still to be searched becomes empty, which happens when first passes last. It never needs to look at every item.

Mark scheme
  1. 1 mark

    Eleri (index 4) is compared first

    The names must be in the correct order. Accept indexes clearly identified (4, 6, 5).

  2. 1 mark

    then Gethin (index 6)

  3. 1 mark

    then Ffion (index 5)

  4. 1 mark

    Gareth comes after Ffion but before Gethin, so there are no names left to search / first becomes greater than last (first = 6, last = 5), so the search ends without finding Gareth

    Do not accept 'it checks every name' or 'it reaches the end of the list' (that describes a linear search).

Question 4

4 marks

A program holds an unsorted list of 50,000 parcel numbers.

Alex says: "We should always sort the list first, so that we can use a binary search instead of a linear search."

Explain whether Alex is right. Refer to how many times the list will be searched.

Model answer

Alex is only partly right. A binary search does need a sorted list, and once it is sorted each search is very fast: at most 16 comparisons for 50,000 items, instead of up to 50,000 for a linear search. But sorting 50,000 items takes a lot of processing. If the list will only be searched once or a few times, it is quicker to use a linear search on the unsorted list. If it will be searched many times, sorting it once and then using binary searches is worth it, as long as the list does not keep changing.

Explanation

The cost of sorting is paid once, but the saving from a binary search is gained on every search. So the right choice depends on how often the data is searched and how often it changes. 50,000 lies between 2 to the power 15 and 2 to the power 16, which is why a binary search needs at most 16 comparisons.

Mark scheme
  1. 1 mark

    a binary search needs the list to be sorted, so it must be sorted before a binary search can be used

    max 4

  2. 1 mark

    sorting 50,000 items takes a lot of time / processing

  3. 1 mark

    if the list is only searched once (or a few times), a linear search on the unsorted list is quicker overall, so Alex is not always right

  4. 1 mark

    if the list is searched many times, sorting it once and then using (fast) binary searches saves time overall

  5. 1 mark

    a binary search of 50,000 items needs at most 16 comparisons, compared with up to 50,000 for a linear search

    accept any sensible comparison of the two searches' efficiency

  6. 1 mark

    if parcels are added or changed often, the list must be kept sorted, which is extra work

Ready to try the rest? Every answer you write is marked against the mark scheme, so you can see exactly where the marks are.

Study Helper Hints first, answers after you try

Stuck on this one? Ask for a hint and I’ll point you in the right direction, without giving the answer away. Once you’ve checked your answer, I’ll show you how the marks are awarded.