Linear and binary search in code

Knowing how a search works is one thing; writing and tracing one is what the exam asks. Here are both searches as real Python programs.

Practise this lesson free (7 questions)

Linear search in Python

Check each item from the start until the target is found or the list runs out. The loop has one exit point: it stops when found becomes True or the index reaches the end.
names = ["Ola", "Ben", "Mia", "Raj", "Zoe"]
target = "Raj"
found = False
index = 0
while index < len(names) and not found:
if names[index] == target:
found = True
else:
index = index + 1
if found:
print("Found at", index)
else:
print("Not found")
Output: Found at 3
Linear search works on unsorted lists. In the worst case it checks every item.

Binary search in Python

The list must be sorted. low and high mark the part of the list still being searched; mid is the middle position, found with integer division.
items = [3, 8, 12, 15, 23, 31, 40, 52, 67]
target = 52
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 items[mid] < target:
low = mid + 1
else:
high = mid - 1
if found:
print("Found at", mid)
else:
print("Not found")
Output: Found at 7

Tracing a binary search

A trace table shows the values each time round the loop. Searching for 52:
Found in 3 comparisons. A linear search would need 8.
lowhighmiditems[mid]Action
0842352 is bigger: low = mid + 1
5864052 is bigger: low = mid + 1
78752Found

How efficient are they?

Each binary search comparison halves the part of the list left to search. That is why it is so fast on big lists: 100 sorted items need at most 7 comparisons, and 1000 need at most 10.
Linear search on 1000 items may need 1000 comparisons. But binary search needs the data sorted first, so for a small or unsorted list a linear search can be the better choice.
Worked example

Use the binary search program to search for 15. Give the values of mid in order.

  1. low = 0, high = 8, so mid = 4; items[4] = 23, 15 is smaller, so high = 3.
  2. low = 0, high = 3, so mid = 1; items[1] = 8, 15 is bigger, so low = 2.
  3. low = 2, high = 3, so mid = 2; items[2] = 12, 15 is bigger, so low = 3.
  4. low = 3, high = 3, so mid = 3; items[3] = 15, found.

Answer: 4, 1, 2, 3

Key idea

Linear search checks every item in turn and works on any list. Binary search needs a sorted list and halves the search area each time, using low, high and mid = (low + high) // 2.

Key words
Binary
Base 2: the number system that uses only the digits 0 and 1.
Binary search
Repeatedly checks the middle item of a sorted list and discards half the list.
Linear search
Checks each item in turn from the start of a list until the target is found or the list ends.
Trace table
A table that tracks the value of each variable as an algorithm runs.

All GCSE and International GCSE Computer Science key terms and definitions →

Quick check

Try two quick questions

See if it has sunk in. Answers are marked straight away.

Extra practice

2 more questions

Try each one, then tap to check.

  1. What does this linear search program print?
    names = ["Ola", "Ben", "Mia", "Raj", "Zoe"]
    target = "Zoe"
    found = False
    index = 0
    while index < len(names) and not found:
    if names[index] == target:
    found = True
    else:
    index = index + 1
    if found:
    print("Found at", index)
    else:
    print("Not found")

    Show the answer

    Answer: Found at 4

    Zoe is at index 4 (counting from 0), so it prints Found at 4.

  2. A linear search looks for an item stored at index 8 of a list. How many comparisons does it make to find it?

    Show the answer

    Answer: 9

    It checks indexes 0 to 8: that is 9 comparisons.

Check you have got it

Answer 7 quick questions with instant marking. If you get one wrong, GCSE-ready shows you why and gives you another go. It is free, and you do not need an account.

Practise this lesson free (7 questions)All GCSE and International GCSE Computer Science lessons

Video for this lesson coming soon. Subscribe on YouTube

Sources and references

Checked by the GCSE-ready editorial team, 17 October 2026. Last updated 2 October 2026. Spotted a mistake? Tell us and we will fix it.

What do exam command words like explain and evaluate mean? →

Related lessons