GCSE Computer Science

Linear search and binary search — GCSE Computer Science

Linear search

Linear search checks every item in a list, one at a time, from the start, until it finds the value it's looking for — or reaches the end without finding it. It doesn't need the data to be sorted; it doesn't care about order at all. The trade-off is speed: in the worst case, linear search has to check every single item.

def linear_search(numbers, target):
    for index in range(len(numbers)):
        if numbers[index] == target:
            return index
    return -1

Binary search

Binary search is faster, but it comes with a condition: the data has to already be sorted. It works by repeatedly checking the middle item of the remaining section of the list. If the middle value is too high, the whole top half is discarded; if it's too low, the bottom half is discarded. Each check halves the amount of data left to search — which is why binary search is dramatically faster than linear search on large, sorted lists.

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

Comparing the two

Linear search works on unsorted data, but its worst case checks every item. Binary search needs sorted data first, but its worst case is far smaller — each comparison eliminates half the remaining list, not just one item. On a small list the difference barely matters. On a large one, it's the difference between a search that's instant and one that visibly takes time.

When each is appropriate

Use linear search when the data isn't sorted and sorting it first isn't worth the cost — searching a short list once, for example. Use binary search when the data is already sorted, or will be searched many times, so the one-off cost of sorting it pays for itself.

Pseudocode pattern for both

Linear search:

FOR index ← 0 TO LENGTH(list) - 1
    IF list[index] == target THEN
        RETURN index
    ENDIF
ENDFOR
RETURN -1

Binary search:

low ← 0
high ← LENGTH(list) - 1
WHILE low <= high
    mid ← (low + high) DIV 2
    IF list[mid] == target THEN
        RETURN mid
    ELSE IF list[mid] < target THEN
        low ← mid + 1
    ELSE
        high ← mid - 1
    ENDIF
ENDWHILE
RETURN -1

What examiners actually test

Expect questions asking you to trace either algorithm through a specific list and target value, state how many comparisons a search takes, or explain why binary search requires sorted data. That last requirement is the single most commonly tested fact about binary search — know it cold.