3.1.3 - Binary search and search comparisons

Searching a sorted range

Binary search compares the target with a middle item in a sorted range and, if they differ, continues in the half that could contain the target.

Consider membership numbers sorted into ascending order:

We will use the lower of the two middle indexes when a range has an even number of items. The first middle index is (0 + 7) DIV 2 = 3, containing 18. If the target is 23, it is greater than 18. Every item at index 3 or below is at most 18, so none can be the target. We can discard all those items and continue at indexes 4 to 7.

In that remaining range, the middle index is (4 + 7) DIV 2 = 5, containing 31. Now 23 is smaller than the middle value. Every item at index 5 or above is at least 31, so those items can be discarded. The remaining range is index 4 alone, where the search finds 23.

The method depends on order. In an unsorted collection, a value greater than the middle item might still appear to its left. Discarding that side could discard the target. Binary search therefore requires sorted data; the rules below are for ascending order.

Other correct implementations can choose the upper middle item instead. That can change a trace. When answering a question, follow its supplied algorithm, stated middle rule and index convention rather than assuming every implementation makes exactly the same comparisons.

Tracing boundary updates

The variables low and high can track the inclusive indexes of the remaining search range. Each unsuccessful middle comparison must remove the checked item and the side that cannot contain the target.

This version reports a matching index or −1:

low ← 0
high ← LEN(data) - 1
position ← -1
WHILE low ≤ high AND position = -1
    middle ← (low + high) DIV 2
    IF data[middle] = target THEN
        position ← middle
    ELSE IF data[middle] < target THEN
        low ← middle + 1
    ELSE
        high ← middle - 1
    ENDIF
ENDWHILE
OUTPUT position

DIV 2 produces a whole-number index. For a target greater than the middle value, low ← middle + 1 starts beyond the item just checked. For a smaller target, high ← middle - 1 ends before it. Updating a boundary to middle instead could keep checking the same item and fail to make progress.

For target 23 in the eight-item array, record the boundaries at the start of each iteration:

The search makes three item comparisons and outputs 4. It allows low = high, because one item remains to check. A condition of low < high would incorrectly stop before that final comparison.

For target 24, the first two rows are the same. The third comparison uses 23 at index 4; 24 is greater, so low becomes 5. Now low > high because 5 > 4. The range is empty, the loop stops and position remains −1. The search does not keep going into an invalid range. For an empty array, high starts at −1 and the body never runs.

This is a Python Study demonstration of the pseudocode's method. Python uses //, <= and == for the corresponding operations. The trace prints show the range before each update, so compare them with the table using the same recording point.

Choosing a search method

Choose a search method by considering the order and size of the data, the number of searches needed and the work performed for likely targets.

For the sorted eight-item example, linear search finds 23 at index 4 after five comparisons; our binary search needs three. However, linear search finds 3 at the first index after one comparison, while our binary search checks 18, then 7, then 3. Binary search is not guaranteed to win for every individual target.

For a large sorted directory that is searched repeatedly, binary search is usually a good choice because each middle comparison discards roughly half of the remaining possibilities. Linear search can require many sequential checks, especially when a target is absent or near the end. If a small unsorted collection is searched only once, sorting it just to use binary search may add more work than simply searching it linearly.

Apply the same reasoning in unfamiliar settings. A warehouse may keep product codes in ascending order for repeated lookups, while a short list of the most recently scanned codes may be unsorted. The stored format and required operations determine which search is suitable.