Binary Search Basics

Guess the middle of the range and compare. Because the data is sorted, one comparison tells you which half cannot contain the target, and that half is thrown away. Searching for 9 in [-1, 0, 3, 5, 9, 12]:

Each step halves the range, so n elements need about log₂ n steps: O(log n).

When you are looking for one specific value, keep a closed range [lo, hi] that still might contain it:

1. Start with lo = 0 and hi = n - 1.
2. Loop while lo <= hi, that is, while the range is not empty.
3. If nums[mid] is the target, return it. If it is smaller, the target can only be to the right, so lo = mid + 1. If it is larger, hi = mid - 1.
4. If the loop ends, the range is empty and the target is not there.

Both updates move past mid, because mid has been checked and is not the answer. See Binary Search for this template in full.

Many problems do not ask "where is x?" but "where does something start?": the first value that is at least x, the first bad version, the smallest speed that is fast enough. Write the question as a yes/no test for each position. Because the data is sorted, the answers line up like this:

false, false, false, true, true, true

The goal is the first true. Use a half-open range [lo, hi), where hi starts one past the last position, meaning "no position is true":

1. Loop while lo < hi.
2. If the test is true at mid, the first true is mid or earlier: hi = mid. Do not skip mid, it may be the answer.
3. If the test is false at mid, the first true is after it: lo = mid + 1.
4. When lo == hi, that position is the answer.

This template has no "found it" case and no special exit, so it is hard to get wrong. Written once with a test function, it solves many problems:

import java.util.function.IntPredicate;

public class FirstTrue {

    // Smallest x in [lo, hi] for which ok(x) is true, or hi + 1 if there is none.
    // Requires ok to be monotone: false, false, ..., false, true, true, ..., true
    public static int firstTrue(int lo, int hi, IntPredicate ok) {
        int left = lo;
        int right = hi + 1;                     // hi + 1 stands for "never true"
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (ok.test(mid)) {
                right = mid;                    // mid is true: the answer is mid or earlier
            } else {
                left = mid + 1;                 // mid is false: the answer is after mid
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 3, 5, 8};
        // first index whose value is >= 3
        System.out.println(firstTrue(0, nums.length - 1, i -> nums[i] >= 3));   // 1
        // smallest x with x * x >= 50
        System.out.println(firstTrue(0, 50, x -> x * x >= 50));                  // 8
    }
}

Binary search does not need an array. It works on any range of candidate answers where a yes/no test changes only once. Take Koko Eating Bananas: "can Koko finish in time at speed s?"

• If speed 4 is fast enough, every speed above 4 is also fast enough.
• If speed 3 is too slow, every speed below 3 is too slow.

So the answers for speeds 1, 2, 3, ... look like false, false, false, true, true, ..., and Template 2 finds the first speed that works. The work is:

1. Find the smallest and largest possible answers.
2. Write a function that checks one candidate answer, usually in O(n).
3. Binary search for the first candidate that passes.

The total is O(n log R), where R is the size of the answer range. This one idea solves a large group of problems: shipping capacity, book allocation, bouquets, divisors, train speeds and more.

• Overflow in mid. (lo + hi) / 2 overflows when both are large, which is why it is written lo + (hi - lo) / 2. Java's own Arrays.binarySearch had this bug until 2006.
• An infinite loop. If one branch sets lo = mid, round mid up with lo + (hi - lo + 1) / 2. Otherwise, with two elements left, mid equals lo and the range never shrinks.
• Mixing the templates. lo <= hi goes with hi = mid - 1; lo < hi goes with hi = mid. Combining lo <= hi with hi = mid loops forever.
• Overflow in the test. Checks like mid * mid <= x overflow an int; compute them in long.

For a sorted array, Java has Arrays.binarySearch. It returns the index if found and -(insertion point) - 1 if not, and with duplicates it may return any of the equal elements, so problems about first or last positions still need your own search.