Binary search

How Binary Search Works

A binary search finds a target value in a list by repeatedly halving the search range. Rather than checking items one at a time, it jumps to the midpoint of the current range and compares the midpoint value to the target. Depending on the result, it either reports a match or discards the half of the list that cannot contain the target. This makes binary search much faster than linear search for large, sorted lists.

There is one critical requirement: the list must be sorted before a binary search can be applied. If the data is not in order, the algorithm cannot reliably eliminate halves and will produce incorrect results.

The Algorithm

The pseudocode below describes the binary search algorithm. Positions are numbered 1 to n.

low ← 1
high ← n
found ← FALSE
WHILE low <= high AND found = FALSE
    mid ← (low + high) DIV 2
    IF list[mid] = target THEN
        found ← TRUE
        position ← mid
    ELSE IF target < list[mid] THEN
        high ← mid - 1
    ELSE
        low ← mid + 1
    ENDIF
ENDWHILE
IF found = TRUE THEN
    OUTPUT position
ELSE
    OUTPUT "Not found"
ENDIF

Each pass through the loop calculates a new midpoint using the current low and high boundaries. The keyword DIV means integer division - any remainder is discarded, so the midpoint is always a whole-number position. After each comparison, either a match is found or one half of the remaining range is permanently eliminated.

Step-by-Step: Three Scenarios

The sorted list below is used in all three examples: [2, 5, 8, 12, 16, 23, 38, 56, 72] (9 items). Each step is shown as a single row - colour indicates the current state of each position:

Grey Eliminated - outside current search range Yellow Current midpoint being checked Red Just discarded this half Green Match found

Target: 16 (position 5). Found in 1 comparison - the best case.

Pass 1: low = 1, high = 9, mid = (1+9) DIV 2 = 5. list[5] = 16 = target. Match!

P1	P2	P3	P4	P5	P6	P7	P8	P9
2	5	8	12	16 ✓	23	38	56	72

Output: Position 5. The target happened to sit exactly at the midpoint of the full list, so only 1 comparison was needed.

Target: 56 (position 8). Found after 3 comparisons.

Pass 1: low = 1, high = 9, mid = 5. list[5] = 16. Target 56 > 16, so search the right half: low ← 6

P1	P2	P3	P4	P5	P6	P7	P8	P9
2	5	8	12	16	23	38	56	72

Pass 2: low = 6, high = 9, mid = (6+9) DIV 2 = 7. list[7] = 38. Target 56 > 38, so search the right half: low ← 8

P1	P2	P3	P4	P5	P6	P7	P8	P9
2	5	8	12	16	23	38	56	72

Pass 3: low = 8, high = 9, mid = (8+9) DIV 2 = 8. list[8] = 56 = target. Match!

P1	P2	P3	P4	P5	P6	P7	P8	P9
2	5	8	12	16	23	38	56 ✓	72

Output: Position 8. Only 3 comparisons to search 9 items - compare this to a linear search which would need 8 comparisons for the same target.

Target: 20 - not present. The search range shrinks to nothing after 4 comparisons.

Pass 1: low = 1, high = 9, mid = 5. list[5] = 16. Target 20 > 16, so low ← 6

P1	P2	P3	P4	P5	P6	P7	P8	P9
2	5	8	12	16	23	38	56	72

Pass 2: low = 6, high = 9, mid = 7. list[7] = 38. Target 20 < 38, so high ← 6

P1	P2	P3	P4	P5	P6	P7	P8	P9
2	5	8	12	16	23	38	56	72

Pass 3: low = 6, high = 6, mid = 6. list[6] = 23. Target 20 < 23, so high ← 5

P1	P2	P3	P4	P5	P6	P7	P8	P9
2	5	8	12	16	23	38	56	72

Pass 4: low = 6, high = 5. Now low > high - the condition low <= high is false. Loop ends.

Output: "Not found". The search range has been reduced to nothing. The value 20 falls between 16 and 23, which are adjacent items - there is no position where it could exist.

Key Takeaways

A binary search works by repeatedly halving the search range, checking the midpoint each time.
The list must be sorted before a binary search can be applied - this is a hard requirement.
After each comparison, one half of the remaining range is permanently eliminated.
The midpoint is calculated as (low + high) DIV 2 using integer division.
The loop ends when either a match is found (found = TRUE) or the search range is empty (low > high).
Binary search is more efficient than linear search for large lists, but requires the extra step of sorting the data first.