Binary search

Someone hands you a sorted list of a million numbers and asks whether one value is in it. Checking every entry answers that in a million comparisons. Asking about the middle entry answers it in about twenty, because every answer throws away half of what is left. The catch sits in the word sorted: run the fast version on a list nobody sorted and it does not crash, it does not warn, it returns an index that is wrong.

Linear search already gave you the walk-and-compare loop and the -1 that means nothing matched, and binary search keeps both while changing only which slots get read.

Binary search requires a sorted array

Student can state that binary search requires the array to be sorted in non-decreasing order, predict the consequence of running it on unsorted data (undefined, often wrong), and decide whether binary or linear search is the right tool given an "is the data already sorted? how many times will I search?" decision.

Seven numbers in order: {1, 3, 5, 7, 9, 11, 13}. Compare a target against the middle one, 7. If the target is larger, the three slots left of 7 are out in one comparison, unread. That move is the entire speedup, and it is legal only because the order makes it true.

Java ships this search as Arrays.binarySearch, in java.util.Arrays. Hand it a sorted int[] and a target and it returns the slot the target sits in, or a negative number when it is absent. Now take the order away.

final int[] scrambled = {9, 1, 13, 3, 11, 5, 7};
System.out.println(Arrays.binarySearch(scrambled, 9));

It prints -8, with a 9 in slot 0 the whole time. No exception, no warning, just a number that is not true. Java's own documentation does not call that wrong, it calls it undefined: "If it is not sorted, the results are undefined."

Sort once, search many times

Sorting is not free, so the two algorithms pay at different moments. The costs below are big-O notation: how the work grows as the array grows, with n the number of slots. O(n) means double the array, double the work. O(log n) means double the array, add one step. O(n log n) is what a sort costs, well above O(n).

• Linear search: no preparation, O(n) on every search.
• Binary search: O(n log n) once to sort, then O(log n) on every search after.

One search, and the sort is wasted. A thousand searches over the same data, and it is repaid many times over. The question to settle first is not which runs faster, it is how many times the data gets asked about.

Sorted means non-decreasing

Sorted means one particular comparison, and it has to be the comparison the search makes. For int[] that is non-decreasing order, xs[0] <= xs[1] <= xs[2] and onward, equal values allowed, so {1, 1, 2, 2, 3} counts. Reverse those seven and the results go undefined again, because xs[mid] > target stops meaning the target is to the left.

The speed has a price: one sort buys O(log n) on every search after it, and skipping it leaves the same fast code returning a number with nothing behind it.

Half the search range each step

Student can trace a binary search step by step on a small sorted array, showing the values of low, high, mid, and the comparison at each iteration; and produce the loop with the correct mid calculation, low <= high continuation condition, and mid + 1 / mid - 1 updates.

The array never changes during a binary search. What changes is a pair of indices marking the part still worth looking at: low at the bottom, high at the top, everything between them in play.

Each pass reads the middle slot of that range, then moves low or high past the half the comparison ruled out, until the target turns up or low passes high, which is what an empty range looks like.

A million slots become half a million, then a quarter million, and about twenty passes later one slot is left. Twenty, because two multiplied by itself twenty times is about a million. O(log n) is the name for that shape.

public static int binarySearch(final int[] xs, final int target) {
    int low  = 0;
    int high = xs.length - 1;
    while (low <= high) {
        final int mid = low + (high - low) / 2;
        if (xs[mid] == target) {
            return mid;
        } else if (xs[mid] < target) {
            low = mid + 1;            // target, if present, is in the right half
        } else {
            high = mid - 1;           // target, if present, is in the left half
        }
    }
    return -1;
}

The trace, one row per pass

The array does not move, so a trace records only low, high, mid, and what the comparison decided. Searching those seven values for 9:

pass 1:  low=0  high=6  mid=3  xs[3]=7  < 9  → low = 4
pass 2:  low=4  high=6  mid=5  xs[5]=11 > 9  → high = 4
pass 3:  low=4  high=4  mid=4  xs[4]=9  == 9 → return 4

Three passes against five. A slot-by-slot walk reads 1, 3, 5, 7, 9 before it stops, and that gap is what grows.

Three places the loop goes wrong

Each of these compiles and runs.

The third is mid = (low + high) / 2, the midpoint as arithmetic suggests writing it. Write low + (high - low) / 2: the subtraction is never negative, so the result cannot run off the top of an int.

The loop ends when low > high, an empty range, so nothing could match and the method returns -1. The JDK's own version usually returns some other negative number, and what those mean comes next.

The range closes either way: low and high close in whether or not the target is there, which is why the loop cannot run more than about twenty times on a million slots.

Arrays.binarySearch: the JDK built-in

Student can call java.util.Arrays.binarySearch correctly on an int[], predict the return for both "found" and "not found" cases using the -(insertionPoint) - 1 rule, and decode a negative return into an insertion point.

The hand-written loop returns -1 for every miss, which answers one question and throws away another. The array was sorted, so the search knows more than absent: it knows where the value would have gone.

final int[] xs = {1, 3, 5, 7, 9, 11, 13};

System.out.println(Arrays.binarySearch(xs, 9));    // prints   4
System.out.println(Arrays.binarySearch(xs, 8));    // prints  -5
System.out.println(Arrays.binarySearch(xs, 0));    // prints  -1
System.out.println(Arrays.binarySearch(xs, 14));   // prints  -8

Zero or higher is an index and the value was found there. Negative means absent, and the number carries the insertion point, the slot the value would occupy to keep the array sorted, encoded as -(insertionPoint) - 1. Decode it with int ip = -result - 1;.

This encoding is stranger than a flat -1, and it exists because some callers need the insertion point: anything maintaining a sorted array wants to know where a new value goes, and the search already worked it out.

A negative return is a location: the sign says whether the value is there, and the magnitude says where it is or where it would go.