Binary Search

A linear search has to look at every element one by one. For a list of a million items, that's potentially a million comparisons. Binary search finishes the same job in about twenty comparisons. The cost is that the list must already be sorted.

Suppose someone asks: "Is the number 23 in this sorted list?"

List:  [ 3, 7, 11, 15, 19, 23, 27, 31, 35 ]
Index:   0  1   2   3   4   5   6   7   8

# Step 1: mid = (0+8)//2 = 4 -> arr[4] = 19. 19 < 23, so discard left half.
#          low = 5, high = 8
# Step 2: mid = (5+8)//2 = 6 -> arr[6] = 27. 27 > 23, so discard right half.
#          low = 5, high = 5
# Step 3: mid = (5+5)//2 = 5 -> arr[5] = 23. 23 == 23 -> FOUND at index 5!

Try binary search yourself. Change the sorted array and target, then click Start. Use Step for manual control or Play for auto-run. Watch how the range (low/high) narrows and elements get discarded (greyed out) with each comparison.

1low = 0
2high = len(data) - 1
3while low <= high:
4    mid = (low + high) // 2
5    if data[mid] == target:
6        return mid
7    elif data[mid] < target:
8        low = mid + 1
9    else:
10        high = mid - 1
11return -1

Now we turn the description into code. The Cambridge pseudocode below is almost identical to the one in the published mark scheme for 9618/22 M/J 2025 Q7(a).

FUNCTION BinarySearch(BYREF dataList : ARRAY OF INTEGER, target : INTEGER) RETURNS INTEGER
    DECLARE low, high, mid : INTEGER
    low <- 0
    high <- LENGTH(dataList) - 1

    WHILE low <= high
        mid <- (low + high) DIV 2
        IF dataList[mid] = target THEN
            RETURN mid
        ELSE
            IF dataList[mid] < target THEN
                low <- mid + 1
            ELSE
                high <- mid - 1
            ENDIF
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

def binary_search(data_list, target):
    low = 0
    high = len(data_list) - 1

    while low <= high:
        mid = (low + high) // 2
        if data_list[mid] == target:
            return mid
        elif data_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # not found

A trace table tracks low, high, mid, and the comparison result for each iteration. This is what examiners ask you to fill in on Paper 4.

Recursion replaces the WHILE loop with the function calling itself, each time on a smaller range. Instead of moving Low and High with assignments, we pass new values as parameters.

FUNCTION RecursiveBinarySearch(
    BYREF dataList : ARRAY OF INTEGER,
    low : INTEGER, high : INTEGER,
    target : INTEGER) RETURNS INTEGER

    DECLARE mid : INTEGER

    IF low > high THEN
        RETURN -1  // base case: not found
    ENDIF

    mid <- (low + high) DIV 2

    IF dataList[mid] = target THEN
        RETURN mid  // base case: found
    ELSE
        IF dataList[mid] < target THEN
            RETURN RecursiveBinarySearch(
                dataList, mid + 1, high, target)
        ELSE
            RETURN RecursiveBinarySearch(
                dataList, low, mid - 1, target)
        ENDIF
    ENDIF
ENDFUNCTION

def recursive_binary_search(
        data_list, low, high, target):

    if low > high:  # base case: empty
        return -1

    mid = (low + high) // 2

    if data_list[mid] == target:
        return mid  # base case: found
    elif data_list[mid] < target:
        return recursive_binary_search(
            data_list, mid + 1, high, target)
    else:
        return recursive_binary_search(
            data_list, low, mid - 1, target)

Each iteration of binary search halves the remaining range:

after 1 step: n / 2 elements left
after 2 steps: n / 4 elements left
after 3 steps: n / 8 elements left
after k steps: n / 2^k elements left

The loop ends when n / 2^k <= 1, so k ≈ log2(n).

Study the pseudocode below. It is supposed to perform a binary search, but it contains four errors. Find each one, give the line number, explain what is wrong, and write the correction.

01  FUNCTION BinarySearch(BYREF B : ARRAY OF INTEGER, target : INTEGER) RETURNS INTEGER
02      DECLARE low, high, mid : INTEGER
03      low <- 0
04      high <- LENGTH(B)                    // ERROR 1
05      WHILE low < high                     // ERROR 2
06          mid <- (low + high) DIV 2
07          IF B[mid] = target THEN
08              RETURN mid
09          ELSE
10              IF B[mid] < target THEN
11                  low <- mid               // ERROR 3
12              ELSE
13                  high <- mid              // ERROR 4
14              ENDIF
15          ENDIF
16      ENDWHILE
17      RETURN -1
18  ENDFUNCTION

A school's library system stores 10,000 book records in a sorted 1D array Catalogue indexed from 0 to 9999. Each element holds a unique 5-digit ISBN (integer). The system uses binary search to find a book by its ISBN.

Fifteen exam-style binary search tasks. Each shows only the question — click Hint for the thought process, or Help for the worked solution.