Skip to main content
EnglandComputer ScienceSyllabus dot point

How do linear search and binary search work, and when is each one the right choice?

The linear search and binary search algorithms, how each works, the requirement that binary search needs sorted data, and how their efficiency compares.

An Eduqas GCSE Computer Science answer on the linear and binary search algorithms: how each works step by step, why binary search needs sorted data, and how their efficiency compares.

Generated by Claude Opus 4.810 min answer

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section
  1. What this dot point is asking
  2. Linear search
  3. Binary search
  4. How the efficiency compares
  5. Try this

What this dot point is asking

Eduqas wants you to describe the linear search and the binary search, explain how each works, state that binary search needs sorted data, and compare their efficiency. Describe-and-compare questions are the norm, and the key marks are the "halve and discard" idea for binary search and the sorted-data requirement.

found = False
for i = 0 to length - 1
  if list[i] == target then
    found = True
    output "Found at position", i
  endif
next i
if found == False then
  output "Not found"
endif

How the efficiency compares

Try this

Q1. State one situation where a linear search is the better choice. [1 mark]

  • Cue. When the list is small or unsorted (binary search would need sorting first).

Q2. State why a binary search needs the data to be sorted. [1 mark]

  • Cue. It discards a half based on whether the target is bigger or smaller than the middle, which only works if the data is in order.

Q3. In a sorted list of 8 items, state roughly how many comparisons a binary search needs at most. [1 mark]

  • Cue. About 3 (each step halves 8 to 4 to 2 to 1).

Exam-style practice questions

Practice questions written in the style of WJEC Eduqas exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Eduqas Component 1, 20224 marksDescribe how a binary search finds a value in a sorted list, and state why the list must be sorted.
Show worked answer →

How it works (up to 3 marks): look at the middle item of the sorted list; if it is the target, stop; if the target is smaller, repeat on the lower half; if larger, repeat on the upper half; keep halving until found or no items remain.

Why sorted (1 mark): the algorithm decides which half to discard based on whether the target is bigger or smaller than the middle, which only works if the items are in order.

Markers reward the "check the middle, discard half, repeat" description and the point that discarding a half relies on the data being sorted.

Eduqas Component 1, 20234 marksCompare linear search and binary search, giving one advantage of each.
Show worked answer →

Linear search advantage (up to 2): works on any list, sorted or unsorted, and is simple to write; good for small or unsorted data.

Binary search advantage (up to 2): much faster on large sorted lists because it halves the items to check each step, so it needs far fewer comparisons.

To compare: linear checks each item in turn (slow on large lists but no sorting needed); binary halves the search each time (fast) but requires the list to be sorted first. Markers reward an advantage tied to each, plus the sorted-data requirement of binary search.

Related dot points

Sources & how we know this