Binary Search

AQA 4.3.4 — Binary search

Binary search repeatedly halves a sorted list, comparing the target to the middle item.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Because it eliminates half the remaining items each step, binary search is O(log n) — dramatically faster than linear search on large lists, but it requires sorted data.

Worked trace

Searching for 23 in [4, 9, 15, 23, 42, 56, 71]:

Only one comparison, because 23 happened to be the middle value.

Linear vs binary — the trade-off

Binary search's speed comes at a cost: the data must already be sorted (which itself takes time — see Bubble Sort and Insertion Sort later in this sequence), and it only works efficiently on structures that support fast middle-element access (arrays, not linked lists). Choosing between them is a genuine algorithm-design decision, not just "binary is always better".

Challenge

Trace binary search for target 56 in the same list, showing low, high and mid at each step.