Lesson 4.3.4.1

4.3.4.1 Linear and binary search Quiz: AQA Computer Science, Unit 3

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 4.3.4.1, Linear and binary search: 20 multiple choice questions for the AQA Computer Science (7517), Unit 3: Fundamentals of algorithms, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. Linear search has which time complexity?

    • O(n)
    • O(1)
    • O(n log n)
    • O(log n)

  2. Binary search has which time complexity?

    • O(log n)
    • O(1)
    • O(n log log n)
    • O(n)

  3. Binary search requires the data to be in which state?

    • Unsorted
    • Stored in a linked list
    • Sorted
    • Containing a single data type only

  4. Which search examines each element in turn from the start of the list?

    • Binary search
    • Linear search
    • Hash search
    • Binary tree search

  5. In binary search, the middle element is less than the target. Which half is searched next?

    • The right half
    • The target is returned at once
    • The list is sorted again
    • The left half

  6. Which search is most suitable for an unsorted list of one million items searched once?

    • Linear search
    • Binary search on a sorted copy only
    • Binary search
    • Binary tree search

  7. Binary search for 23 is applied to the sorted list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. How many comparisons are made?

    • 3
    • 2
    • 1
    • 4

  8. Linear search for 91 in the sorted list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] is performed. How many comparisons are made?

    • 9
    • 10
    • 5
    • 100

  9. What is the maximum number of comparisons needed by binary search on a sorted list of 1024 items?

    • 512
    • 1024
    • 10
    • 5

  10. A linear search of an unsorted list of 500 items finds a target that is present, on average. How many comparisons are needed on average?

    • 500
    • 250
    • 1
    • 250000

  11. Roughly how many comparisons does binary search need in the worst case on one million sorted items?

    • 10
    • 20
    • 500000
    • 1000

  12. Why can sorting once and then using binary search be better than linear search for many searches?

    • Sorting makes each search cost O(n)
    • Binary search works on unsorted data
    • Linear search becomes O(log n) once data is sorted
    • Sorting is a one-off cost, after which each binary search costs O(log n)

  13. Binary search for 4 is applied to the sorted list [1, 3, 5, 7, 9, 11]. How many comparisons are made before the search ends?

    • 4
    • 2
    • 3
    • 6

  14. Which expression gives the worst-case number of comparisons for binary search on n sorted items?

    • log2 n, rounded up
    • n
    • n squared
    • n / 2

  15. A binary search is run on 15 sorted items for a value that is not present. What is the maximum number of comparisons?

    • 15
    • 4
    • 3
    • 5

  16. For a sorted list of 1,000,000 items in the worst case, which statement is correct?

    • Both need exactly 1,000,000 comparisons
    • Linear search is faster for all n
    • Binary search needs about 20 comparisons, whereas linear search may need up to 1,000,000
    • Binary search needs 1,000,000 comparisons but linear search needs 20

  17. Why does binary search fail to work on an unsorted list?

    • The midpoint comparison cannot tell which half could contain the target
    • Lists cannot be divided into halves
    • The index must be an odd number
    • Binary search only works on numbers

  18. Binary search for 60 is applied to the sorted list [10, 20, 30, 40, 50, 60, 70] using zero-based indexing. At which index is 60 found?

    • 60
    • 6
    • 5
    • 4

  19. Binary search repeatedly halves the search space. Which base is used for the logarithm in O(log n)?

    • Base 10 always
    • Base 2, because the search space halves each step
    • Base n
    • Base e always

  20. A sorted list of 1023 items is searched using binary search in the worst case. How many comparisons are needed at most?

    • 10
    • 50
    • 511
    • 11

All AQA Computer Science quizzes