Searching: linear search and binary search

Linear search

Check each item in turn from the start until the target is found or the end is reached.

• Works on unsorted data. Simple.
• Up to n comparisons for n items (slow for large lists).
• On a sorted list it can stop early as soon as it passes an item larger than the target, because the target cannot appear later.

In [27, 14, 39, 8, 51, 23, 6], searching for 8 takes 4 comparisons; searching for 30 takes all 7 and reports 'not found'.

Binary search (iterative)

Requires sorted data.

1. Set low = 0 and high = last index.

2. While low <= high: mid = (low + high) // 2.

3. If list[mid] is the target, it is found.

4. If list[mid] < target, set low = mid + 1 (discard the lower half); otherwise set high = mid - 1.

5. If low > high, the target is not in the list.

Each comparison halves the remaining items, so about log2 n comparisons are needed: 1 000 000 items need about 20.

Searching [3, 8, 12, 19, 24, 31, 40, 47, 55, 62] for 47: found at index 7.

Binary search (recursive)

def bsearch(lst, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif lst[mid] < target:
        return bsearch(lst, target, mid + 1, high)
    else:
        return bsearch(lst, target, low, mid - 1)

The base cases are 'found' and 'low > high'. Each recursive call works on half of the previous range. Searching for 12 in the list above makes calls with (low, high) = (0, 9), (0, 3), (2, 3).

Worked example

Trace a binary search for 20 in [3, 8, 12, 19, 24, 31, 40, 47, 55, 62].

1. low = 0, high = 9, mid = 4, list[mid] = 24: too big, high = mid - 1
2. low = 0, high = 3, mid = 1, list[mid] = 8: too small, low = mid + 1
3. low = 2, high = 3, mid = 2, list[mid] = 12: too small, low = mid + 1
4. low = 3, high = 3, mid = 3, list[mid] = 19: too small, low = mid + 1
5. low > high, so the loop ends

Answer: 20 is not in the list (return -1).

Check yourself

1. A linear search looks for 23 in [27, 14, 39, 8, 51, 23, 6]. How many comparisons are made?
   Show answer

   6. 23 is item 6 in the list.

2. A linear search that stops early looks for 20 in the sorted list [3, 8, 12, 19, 24, 31, 40, 47, 55, 62]. How many comparisons are made before it stops?
   Show answer

   5. It checks 3, 8, 12, 19, then 24 > 20, so it stops after 5 comparisons.

3. Binary search on [3, 8, 12, 19, 24, 31, 40, 47, 55, 62] (indexes 0 to 9). What is the index of the first mid point?
   Show answer

   4. (0 + 9) // 2 = 4.

4. How many items are compared with the target when binary search looks for 47 in [3, 8, 12, 19, 24, 31, 40, 47, 55, 62]?
   Show answer

   2. Mid values checked: 24, 47.

5. Binary search looks for 62 in [3, 8, 12, 19, 24, 31, 40, 47, 55, 62]. What is the value of mid when 62 is found?
   Show answer

   9. Trace (low, high, mid): (0, 9, 4), (5, 9, 7), (8, 9, 8), (9, 9, 9).

6. What must be true of the data before a binary search can be used?
   • It must contain an even number of items
   • It must contain only unique items
   • It must be sorted
   • It must be stored in a dictionary
   Show answer

   It must be sorted. Discarding half the list only works if the order is known.

7. Why is binary search usually faster than linear search on a large sorted list?
   • Each comparison halves the number of items left to search
   • It checks two items at once
   • It starts from the end of the list
   • It does not compare any items
   Show answer

   Each comparison halves the number of items left to search. About log2 n comparisons instead of up to n.

8. A sorted list has 2²⁰ items. What is the maximum number of comparisons a binary search needs (log2 n + 1)?
   Show answer

   21. log2(2²⁰) = 20, plus one: 21.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (2026)
• Pearson Edexcel IAL Computer Science IAS sample assessment materials (Unit 1, WCP01)

Last updated 8 November 2026. Spotted a mistake? Tell us.