Binary search

Binary search finds a value in sorted data (values in order, for example smallest to largest) by looking at the middle and throwing away the half that cannot hold the answer. Each step halves the work, so 100,000 values need at most 17 looks and a billion need about 30. That slow growth is written O(log n); the notation is explained in Basics and maths. Interviewers ask it often because the idea is simple but the code is famous for off-by-one bugs, and because its "search on the answer" form solves many harder problems. Two templates avoid the bugs.

Template 1: find an exact value

Keep a window from low to high, both inclusive. While the window is not empty (low <= high), look at the middle. If it is the target, return its position. If it is smaller, the target can only be to the right, so move low to mid + 1. Otherwise move high to mid - 1. When the window is empty, the target is not there. The picture shows a search for 63 among 15 sorted values.

Three bugs to avoid: writing low < high skips the last one-value window; writing low = mid instead of mid + 1 can loop forever; and in Java, (low + high) / 2 overflows when both are large, so write low + (high - low) / 2. Python integers do not overflow, so (low + high) // 2 is fine there.

Template 2: lower bound

Most variants are easier with a second template: find the first position whose value is at least the target. Here high starts at the length of the list, because the answer can be "after the last value". While low < high: if the middle value is smaller than the target, the answer is to the right (low = mid + 1); otherwise the middle may be the answer, so keep it (high = mid). When the loop ends, low is the answer. It answers several questions at once:

• Search insert position is exactly the lower bound.
• Is the target present? Check that the lower bound is inside the list and holds the target.
• First and last position of a repeated value: the first is the lower bound of the target, the last is one before the lower bound of target + 1.

Python's bisect.bisect_left is the lower bound. Java's Arrays.binarySearch returns the position when the value is found, and minus the insertion point minus one when it is not. The program below compares a hand-written lower bound with the built-in versions.

import java.util.Arrays;

public class Main {
    static int lowerBound(int[] nums, int target) {
        int low = 0;
        int high = nums.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 3, 3, 5, 6};
        System.out.println(lowerBound(nums, 3) + " " + (lowerBound(nums, 4) - 1));
        System.out.println(lowerBound(nums, 4) + " " + lowerBound(nums, 9));
        System.out.println(Arrays.binarySearch(new int[] {1, 3, 5, 6}, 2));
    }
}

1 3
4 6
-2

import bisect


def lower_bound(nums, target):
    low, high = 0, len(nums)
    while low < high:
        mid = (low + high) // 2
        if nums[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low


nums = [1, 3, 3, 3, 5, 6]
print(lower_bound(nums, 3), lower_bound(nums, 4) - 1)
print(lower_bound(nums, 4), lower_bound(nums, 9))
print(bisect.bisect_left([1, 3, 5, 6], 2))

1 3
4 6
1

The value 3 first appears at position 1 and last at position 3. The value 4 would be inserted at position 4, and 9 after the end, at position 6. Java reports the missing 2 as -2, which means "insert at position 1".

Rotated sorted lists

A rotated list is a sorted list whose front part was moved to the back. Such a list, for example 4, 5, 6, 7, 0, 1, 2, is not sorted as a whole, but at every step one half of the window still is. If the first value of the window is at most the middle, the left half is sorted; otherwise the right half is. If the target lies inside the range of the sorted half, search there; if not, search the other half.

Binary search on the answer

The most useful form does not search a list at all. Suppose you can answer a yes-or-no question for any candidate answer, and the answers switch from "no" to "yes" only once as the candidate grows. Then binary search over the candidates. For a square root rounded down, ask "is k × k at most x?". For the smallest truck capacity that ships packages in d days, ask "can this capacity do it?"; a greedy walk (one pass that always takes the simplest choice, here loading packages while they fit) answers that, and a larger capacity never needs more days. Set the range of possible answers, write the yes-or-no test as its own function, and use the lower-bound template to find the first "yes".

How to answer in an interview

Say why binary search applies: the data is sorted, or the yes-or-no answers are ordered. Name your template and what low and high mean ("high is one past the last possible answer"). Trace a three-value list by hand, including a target that is missing, then state the cost: O(log n) looks, times the cost of one test when you search on the answer.

Common mistakes

• Mixing the two templates, such as low <= high together with high = mid, which can loop forever.
• Starting high at the last position when the answer can be past the end.
• Overflow (a number too big for its type) in the middle index, or in mid × mid when searching for a square root; compare mid with x / mid instead.
• Walking left and right from a found value to find the first and last copies, which is O(n) on a list of equal values.

Recap

Binary search needs order and a clear meaning for the window ends. Use the exact template to find a value, the lower bound for "first position that is at least", and a binary search over candidates when a yes-or-no test turns true only once.