EnglandComputer ScienceSyllabus dot point

How do linear and binary search work, and why is binary search so much faster on a sorted list?

Searching algorithms: linear search, binary search and binary tree search, how each works with a trace, the precondition for binary search, and their time complexity in Big-O notation.

An OCR H446 answer on searching algorithms: how linear search, binary search and binary tree search work with worked traces, the requirement that binary search needs a sorted list, and the time complexity of each in Big-O notation.

Generated by Claude Opus 4.814 min answerUpdated 2026-06-02

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

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

Quick answer

Linear search checks each item in turn from the start until it finds the target or reaches the end; it works on any list (sorted or not) and has worst-case time complexity $O(n)$ because it may examine all $n$ items. Binary search works only on a sorted list: it compares the target with the middle item, and because the list is ordered it can discard the half that cannot contain the target, repeating until found or the range is empty; halving each step gives $O(\log n)$ . Binary tree search uses a binary search tree: starting at the root, it goes left if the target is smaller and right if larger, taking a path down the tree; it is $O(\log n)$ for a balanced tree but degrades to $O(n)$ if the tree is badly unbalanced. Binary search is far faster than linear search on large sorted data, which is why sorting first is often worthwhile.

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

OCR wants you to describe and trace linear search, binary search and binary tree search, state the precondition for binary search, and give each algorithm's time complexity in Big-O. This is trace-table and complexity territory: expect to complete a trace and to compare complexities.

The answer

Linear search

function linearSearch(list, target)
  for i = 0 to length(list) - 1
    if list[i] == target then
      return i
    endif
  next i
  return -1   // not found
endfunction

Binary search

Binary tree search

Trace a binary search

Search the sorted list $[2, 5, 8, 12, 16, 23, 38, 56]$ (indices 0 to 7) for the value 23 using a trace table.

step 1: Set the initial range

low = 0, high = 7. The list is sorted, so binary search is valid.

step 2: First comparison

$mid = (0 + 7)\ \text{DIV}\ 2 = 3$ ; list[3] = 12. Since $23 > 12$ , discard the lower half: low = 4.

step 3: Second comparison

$mid = (4 + 7)\ \text{DIV}\ 2 = 5$ ; list[5] = 23. Match found at index 5.

step 4: Read off the result and count

The value 23 is at index 5, found in two comparisons. The trace table:

low	high	mid	list[mid]	action
0	7	3	12	$23 > 12$ , low = 4
4	7	5	23	found at index 5

A linear search would have taken six comparisons to reach index 5; binary search took two, illustrating the $O(\log n)$ advantage.

Examples in context

A dictionary or phone book lookup is naturally a binary search, you open in the middle and discard half. Databases index data in balanced trees (B-trees) so lookups are logarithmic. Linear search is used where data is small, unsorted or searched once (sorting first would not pay off). The choice illustrates the trade-off OCR stresses: sorting costs time but enables fast repeated binary searches. This links directly to sorting algorithms and to Big-O analysis.

Try this

Q1. State the precondition that must hold before binary search can be used. [1 mark]

Cue. The list must be sorted.

Q2. State the worst-case time complexity of linear search and of binary search. [2 marks]

Cue. Linear search $O(n)$ ; binary search $O(\log n)$ .

Q3. Explain why binary tree search can degrade to $O(n)$ . [2 marks]

Cue. If the tree is unbalanced (for example built from sorted data into a long chain), its height approaches $n$ , so a search may have to descend $n$ nodes.

Exam-style practice questions

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

OCR 20196 marksA sorted list contains

[3, 7, 11, 15, 19, 23, 27]

(indices 0 to 6). Using a trace table, show how a binary search finds the value 19, and state the time complexity of binary search.

Show worked answer →

Trace (up to 5):

low	high	mid	list[mid]	comparison
0	6	3	15	$15 < 19$ , so search right; low = 4
4	6	5	23	$23 > 19$ , so search left; high = 4
4	4	4	19	found at index 4

Each step computes $mid = (low + high)\ \text{DIV}\ 2$ , compares, and halves the range. The value 19 is found at index 4 after three comparisons.

Complexity (1 mark): binary search is $O(\log n)$ because the search space halves each step. Markers reward a correct trace table with mid recalculated and the range narrowing, and the $O(\log n)$ complexity.

OCR 20216 marksExplain why linear search has time complexity

O(n)

while binary search has

O(\log n)

, and explain the condition that must hold before binary search can be used.

Show worked answer →

Linear search $O(n)$ (up to 2): linear search checks each item in turn from the start; in the worst case (item last or absent) it examines all $n$ items, so the number of comparisons grows in proportion to $n$ .

Binary search $O(\log n)$ (up to 2): binary search compares the target with the middle item and discards half the remaining items each step; the number of steps needed to reduce $n$ items to one is $\log_2 n$ , so the work grows logarithmically.

Condition (up to 2): binary search requires the list to be sorted, because it relies on knowing that everything to one side of the middle is smaller (or larger) than the target. On an unsorted list it cannot decide which half to discard. Markers reward "checks all $n$ in the worst case" for linear, "halves each step" for binary, and the sorted precondition.

Related dot points

Sources & how we know this

OCR AS and A Level Computer Science (H046, H446) specification — OCR (2015)