Linear and binary search

Tracing both searches in pseudocode, recursive binary search, O(n) against O(log n), and when sorting first pays off.

A5.3Algorithms and complexityA level25 min

At GCSE (F5.5 and F5.6) you learned what linear and binary search do and that binary search needs sorted data. At A level you also need to trace them precisely, write them in pseudocode, write binary search recursively, and analyse their time and space complexity.

Linear search

Linear search checks each item in turn until it finds the target or runs out of items. In AQA's pseudo-code:

SUBROUTINE LinearSearch(items, target)
    i ← 0
    WHILE i < LEN(items)
        IF items[i] = target THEN
            RETURN i
        ENDIF
        i ← i + 1
    ENDWHILE
    RETURN -1
ENDSUBROUTINE

Analysis. The basic operation is the comparison items[i] = target, and the loop can run once for each of the n items.

It uses a single index variable whatever n is, so its space complexity is O(1). Its strengths: it works on unsorted data, and on structures you can only walk through in order, such as a linked list or a file of records.

Binary search

Binary search works on a sorted list. It keeps two indexes, low and high, around the part that could still hold the target, and looks at the middle of that part. In OCR's Exam Reference Language:

function binarySearch(items, target)
    low = 0
    high = items.length - 1
    while low <= high
        mid = (low + high) DIV 2
        if items[mid] == target then
            return mid
        elseif target < items[mid] then
            high = mid - 1
        else
            low = mid + 1
        endif
    endwhile
    return -1
endfunction

Tracing it. Search for 52 in the 11 sorted readings [3, 9, 14, 21, 30, 38, 45, 52, 60, 71, 88]:

Searching for 10 in the same list looks at indexes 5, 2, 0 and 1, then low becomes 2 and high is 1. With low > high there is nothing left and it returns -1. In a trace question, keep a column for every variable and use the rounding the question gives (DIV rounds down).

Analysis. Every look throws away the middle item and half of the rest. After 1 look at most n/2 items are left, after 2 looks n/4, after k looks n/2ᵏ. The search must stop once fewer than one item remains, which takes about log₂ n looks. Exactly, the worst case is ⌊log₂ n⌋ + 1 looks:

So binary search is O(log n) in the worst and average case, and O(1) in the best case (the target is the first middle item). The iterative version uses three index variables, so it is O(1) in space.

Binary search by recursion

Each look leaves a smaller problem of exactly the same kind, so binary search can call itself on the half that is left. There are two base cases: the part is empty (not found) or the middle item is the target (found).

def binary_search(items, target, low, high):
    if low > high:
        return -1                                        # base case: nothing left
    mid = (low + high) // 2
    print("  looking at index", mid, "which holds", items[mid])
    if items[mid] == target:
        return mid                                       # base case: found
    elif target < items[mid]:
        return binary_search(items, target, low, mid - 1)
    else:
        return binary_search(items, target, mid + 1, high)

readings = [3, 9, 14, 21, 30, 38, 45, 52, 60, 71, 88]
print("52 is at", binary_search(readings, 52, 0, len(readings) - 1))
print("10 is at", binary_search(readings, 10, 0, len(readings) - 1))

Run this in the simulator

The time complexity is still O(log n): it makes the same looks. But every call waits on the stack for the one it made, so there are up to about log₂ n frames at once, and the space complexity is O(log n) instead of O(1). For binary search that is tiny (30 frames for a billion items), but it is the standard trade-off between recursion and iteration.

Is sorting first worth it?

Binary search needs sorted data, and sorting costs time. A good sort is O(n log n): about 20 million comparisons for a million items. One linear search of the same list averages 500,000 comparisons.

• To search once, just use linear search. Sorting first costs far more than it saves.
• To search many times, sort once and binary search every time. Here the sort pays for itself after about 40 searches.
• If the data changes constantly, keeping it sorted has its own cost, and a hash table (module A3) may beat both.

Choosing a search is a judgement about the data and how it will be used, not a rule that binary search is always better.

Task: recursive binary search

Write binary_search(items, target, low, high) recursively (it must call itself, with no while or for loop inside it). It searches the sorted list items between indexes low and high inclusive, finds the middle with (low + high) // 2, and returns a tuple (index, looks): the index of target, or -1 if it is not there, and the number of middle items it looked at.

items is the 1,000 even numbers 0, 2, 4, ... 1998. Print exactly three lines:

• 734: index <index> after <looks> looks
• 735: not found after <looks> looks
• most looks: <n>, the largest number of looks needed to find any one of the 1,000 items in the list (search for every item to find out).

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

items = list(range(0, 2000, 2))

def binary_search(items, target, low, high):
    return -1, 0

Challenges

1. How many looks does binary search need, at most, for 5,000 items? Work it out, then check it.
2. Change linear search so it stops early on a sorted list once it passes where the target would be. What is its worst case now?
3. Write the recursive binary search in AQA pseudo-code.