Level:
Correct: 0
Incorrect: 0
Marks: 0/0
Exam Practice
Course:
Topics:
AQA GCSE Computer Science (Paper 1) Smart practice A mixed round aimed at your weak spots
Unit 1
3.1 Fundamentals of algorithms
Unit 2
3.2 Programming
Data types
Data types
Arithmetic operations in a programming language
Arithmetic operations, DIV and MOD
Relational operations in a programming language
Relational operations
Boolean operations in a programming language
Boolean operations in conditions
Data structures
Arrays and records
Input/output
Input and output
String handling operations in a programming language
String handling
Random number generation in a programming language
Random number generation
Structured programming and subroutines (procedures and functions)
Subroutines and structured programming
Avg
score:
–
Topics
done:
0/15

Linear search and binary search

Practise 30 exam-style questions on Linear search and binary search for AQA GCSE Computer Science (Paper 1). 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.

  • 30 questions
  • 1–8 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

1 mark

A binary search is used on an array of 16 items with indexes 0 to 15. The index of the middle item is worked out with this line of pseudo-code, where low and high are the first and last indexes still being searched:

mid ← (low + high) DIV 2

Which index is checked first?

Choose your answer.

  • 7
  • 8
  • 7.5
  • 15

Model answer

7

Explanation

At the start low is 0 and high is 15, so mid is 15 DIV 2, which is 7 because DIV gives the whole-number part of the division. 7.5 comes from real division, which cannot be used as an index. 8 is the other central item, which this line of code does not pick.

Mark scheme
  1. 1 mark

    7

    If more than one option is given, 0 marks. Mark is for AO2 (apply).

Question 2

2 marks

In the pseudo-code below, the variable count records how many items of ages have been compared with target.

ages ← [16, 14, 15, 17, 14, 16, 15]
target ← USERINPUT
count ← 0
found ← False
REPEAT
  IF ages[count] = target THEN
    found ← True
  ENDIF
  count ← count + 1
UNTIL found = True OR count = LEN(ages)
OUTPUT count

State the output when the user enters 17, and state the output when the user enters 13.

Model answer

17: 4 (16, 14, 15 and 17 are compared, then found is True)
13: 7 (13 is not in the array, so all 7 items are compared and the loop stops when count = LEN(ages))

Explanation

count goes up by 1 after each comparison, so when 17 is found at index 3 the value of count is 4. For 13 there is no match, so the loop only ends when count reaches the length of the array, 7. Giving 3 for the first answer confuses the index of the match with the number of items compared.

Mark scheme
  1. 1 mark

    17: 4

    Both marks AO2 (apply). R. 3 (the index of 17, not the number of comparisons).

  2. 1 mark

    13: 7

    13 is not in the array, so all 7 items are compared.

Question 3

3 marks

The table shows an array called members, which holds names in alphabetical order.

A binary search is used to look for the name Kofi. When an even number of items is left to search, the item just to the left of the centre is used as the middle item.

State the first name that Kofi is compared with, explain why the search can then ignore Aled, Bryony, Cerys and Deepa, and state the second name that Kofi is compared with.

Array: members. Table with columns "Index", "Value". Index: 0; Value: Aled | Index: 1; Value: Bryony | Index: 2; Value: Cerys | Index: 3; Value: Deepa | Index: 4; Value: Ewan | Index: 5; Value: Grace | Index: 6; Value: Kofi | Index: 7; Value: Megan | Index: 8; Value: Niamh.

Model answer

First name compared: Ewan (index 4, the middle of indexes 0 to 8).
Kofi comes after Ewan alphabetically and the array is in alphabetical order, so Kofi cannot be in indexes 0 to 4. Aled, Bryony, Cerys, Deepa (and Ewan) are discarded.
Indexes 5 to 8 are left (an even number of items), so the middle is index 6: the second name compared is Kofi, which is found.

Explanation

Names are compared alphabetically, so a binary search works on them just as it does on numbers. Because Kofi comes after Ewan and the array is sorted, everything up to Ewan can be thrown away. Four names are then left, and the rule in the question picks index 6, Kofi; picking Megan uses the other middle item and ignores the rule given.

Mark scheme
  1. 1 mark

    Ewan (first name compared)

    All marks AO2 (apply).

  2. 1 mark

    Kofi comes after Ewan in alphabetical order, and the names are sorted, so Kofi cannot be before Ewan / the names before Ewan (and Ewan) are discarded

    NE. 'because it halves the list' - the answer must use the alphabetical order of the names.

  3. 1 mark

    Kofi (second name compared, so Kofi is found)

    R. Megan (that uses the item to the right of the centre, not the rule in the question).

Question 4

4 marks

Jade's music app stores 3,000 song titles in the order she downloaded them, and she downloads new songs most days. The app uses a linear search to find a song. A friend suggests changing the app so that it uses a binary search instead.

Explain one advantage and one disadvantage of using a binary search in this app.

Model answer

Advantage: a binary search would find a song more quickly, because each comparison discards half of the songs that are left, so it needs far fewer comparisons than a linear search checking up to 3,000 songs one at a time.
Disadvantage: a binary search only works on sorted data, so the titles would have to be sorted into alphabetical order first, and re-sorted (or each new song inserted in the right place) every time Jade downloads a song, which takes extra processing time.

Explanation

With 3,000 items a binary search needs only a handful of comparisons, because the items left to check halve each time. However, Jade's titles are in download order and change most days, so the cost of sorting and keeping them sorted is a real drawback in this scenario. Each expansion mark needs a reason linked to the point it expands.

Mark scheme
  1. 1 mark

    Advantage: a binary search is quicker / more time-efficient (on average) for a large number of songs

    All marks AO2 (apply). 1 mark for the advantage and 1 mark for its expansion; 1 mark for the disadvantage and 1 mark for its expansion. NE. 'binary search is better' without saying how.

  2. 1 mark

    because each comparison halves the number of songs left to check, so it needs far fewer comparisons than checking up to 3,000 songs one by one

    Expansion of the advantage: only award if the advantage has been given.

  3. 1 mark

    Disadvantage: the song titles would have to be sorted (into alphabetical order) first

    A. 'the program would be more complex to write' as the disadvantage.

  4. 1 mark

    and kept sorted every time a new song is downloaded, which takes extra time / processing // (if the disadvantage given is that the program is more complex to write) it needs extra variables for the bounds and more code to write and test

    Expansion of the disadvantage: only award if the disadvantage has been given.

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.