Searching — Linear & Binary

Spec & Goals 3 min

AQA Spec 3.1.3 · Searching algorithms

By the end of this lesson you can:

1. Describe how a linear search checks each item in turn.
2. Describe how a binary search halves a sorted list each step.
3. Trace a binary search and count the comparisons it makes.

Warm-Up 5 min

Last lesson we measured the efficiency of an algorithm by counting its steps. Today we count comparisons in two ways of searching.

Quick starter

You want to find a friend's name in a phone book. The names are in alphabetical order.

Would you read every name from the start, or open the book in the middle first?

Key Concept — two ways to search 14 min

A searching algorithm finds a value in a list, or confirms the value is not there. AQA expects you to know two of them.

Linear search

A linear search checks each item in turn, starting at the front. It stops when it finds the target or reaches the end of the list.

It works on any list — sorted or not. That is its main strength.

AQA pseudo-code — linear search

found ← False
i ← 0
WHILE i < LEN(list) AND found = False
    IF list[i] = target THEN
        found ← True
    ELSE
        i ← i + 1
    ENDIF
ENDWHILE
OUTPUT found

The same in Python

found = False
i = 0
while i < len(items) and not found:
    if items[i] == target:
        found = True
    else:
        i = i + 1
print(found)

Binary search

A binary search is faster, but the list must be sorted first. It works on the middle item each step.

Each step does one of three things:

• If the middle item is the target — stop, it is found.
• If the target is smaller — discard the upper half.
• If the target is larger — discard the lower half.

Then repeat on the half that remains. Each step roughly halves the list.

AQA pseudo-code — binary search

low ← 0
high ← LEN(list) − 1
found ← False
WHILE low ≤ high AND found = False
    mid ← (low + high) DIV 2
    IF list[mid] = target THEN
        found ← True
    ELSE IF target < list[mid] THEN
        high ← mid − 1
    ELSE
        low ← mid + 1
    ENDIF
ENDWHILE
OUTPUT found

The same in Python

low = 0
high = len(items) - 1
found = False
while low <= high and not found:
    mid = (low + high) // 2
    if items[mid] == target:
        found = True
    elif target < items[mid]:
        high = mid - 1
    else:
        low = mid + 1
print(found)

Worked Example — binary search for 7 12 min

Problem: binary search for 7 in the sorted list [1, 3, 4, 7, 9, 11, 15]. The seven items sit at index 0 to 6.

We set low ← 0 and high ← 6, then halve each step using mid ← (low + high) DIV 2.

mid = (0 + 6) DIV 2 = 3, and list[3] is 7. The target is found on the first comparison.

Now trace a target that takes longer — search for 11 in the same list:

Here 11 is found after 2 comparisons. Marks are earned for the correct mid at each step (1), the correct half discarded (1), and the final comparison count (1).

Try It Yourself 12 min

📝 Exam Practice 10 min

Answer the way the examiner expects — the command word and the marks tell you how much to write.

Recap & Key Terms 3 min

A searching algorithm finds a value in a list. A linear search checks each item in turn and works on any list. A binary search halves a sorted list each step, so it is much faster on large lists.

Searching algorithm

A method to find a value in a list, or report that it is absent.

Linear search

Check each item in turn from the start until the target is found or the list ends. Works on any list.

Binary search

On a sorted list, check the middle item and discard the half that cannot hold the target; repeat.

Sorted list

A list whose items are in order. Binary search requires one; linear search does not.

Homework 1 min

Task (≤ 15 min): Trace a binary search for 4 in the sorted list [1, 3, 4, 7, 9, 11, 15]. Record low, high and mid at each step, and state the number of comparisons.