Binary search

Binary search for coding interviews, on sorted arrays and on the answer. One template that avoids off-by-one bugs, step-throughs of lower bound and Koko eating bananas, code in Java, Python, C#, Go and TypeScript, and 10 LeetCode problems.

Mid-level15 min read

Everyone knows binary search. Look at the middle, throw away half, and repeat. For n sorted items that is about log₂ n looks: a million sorted items take 20 looks instead of a million. Yet it’s one of the most commonly botched pieces of interview code. There are a dozen slightly different versions: < or <=, middle or middle - 1, return low or high. Mixing two of them gives an infinite loop, or an off-by-one.

This page teaches one version. And it teaches it as a question about a yes/no function, not about arrays. That version handles “find the target”, “find the first”, and “find the insert position”. It also handles problems that don’t look like binary search at all: “what’s the smallest speed, capacity or day that works?”

How to spot it

Sorted input and a search: find a value, the first or last occurrence, the insert position, a value in a sorted matrix.
“Minimum X such that…” or “maximum X such that…”, where X is a number (a speed, a capacity, a size, a day), and checking one value of X is a simple loop.
O(log n) required in the statement, which almost always means binary search.
A sorted array that’s been rotated. One half of any split is still sorted, so you can still throw half away.

Watch it run

First, the first position of 5 in a sorted array with duplicates. The question asked at each index is “is nums[index] >= 5?”, which is false, false, true, true… across the array. Watch high keep a candidate rather than skip past it.

nums (target 5)

203152538495126157

low

low, high = 0, len(nums) # answer in [low, high]
while low < high:
middle = (low + high) // 2
if nums[middle] < target: low = middle + 1
else: high = middle # middle might be it
return low # first index with nums[index] >= target

Find the first 5. The answer could be anywhere from 0 to 8 (past the end means "not here").

1 / 5

Then switch to Search the answer. Koko eats bananas from piles at some speed per hour, and must finish in 8 hours. There is no array to search, but “can she finish at this speed?” is false for slow speeds and true for fast ones, flipping once. So the same loop finds the slowest speed that works, testing 4 speeds instead of 11. With piles up to a billion, that’s 30 tests instead of a billion.

The template

One function, first_true, and two uses of it:

BinarySearch.javaexample.pyBinarySearch.csmain.goexample.ts

import java.util.function.IntPredicate;

public class BinarySearch {
    static int firstTrue(int low, int high, IntPredicate predicate) {
        // The one binary search to memorize: predicate is false, ..., false, true, ..., true over
        // [low, high). Return the first value where it is true, or high if it never is. The answer
        // always stays in [low, high], and the range shrinks every step.
        while (low < high) {
            int middle = low + (high - low) / 2; // (low + high) / 2 can overflow int
            if (predicate.test(middle)) high = middle; // middle might be the answer: keep it
            else low = middle + 1; // middle is not: drop it and everything before it
        }
        return low;
    }

    static int lowerBound(int[] nums, int target) {
        // First index whose value is >= target. On a sorted array that flips exactly once.
        return firstTrue(0, nums.length, index -> nums[index] >= target);
    }

    static int minEatingSpeed(int[] piles, int hourLimit) {
        // No array to search, but "finishes in hourLimit hours at this speed" flips from false to
        // true once as speed grows. So search the answer itself, from 1 to the biggest pile.
        int max = 0;
        for (int pile : piles) max = Math.max(max, pile);
        return firstTrue(1, max, speed -> {
            long hours = 0; // a long: many big piles at speed 1 overflow an int
            for (int pile : piles) hours += (pile + speed - 1) / speed; // ceil(pile / speed)
            return hours <= hourLimit;
        });
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 5, 5, 8, 9, 12, 15};
        check(lowerBound(nums, 5) == 2);
        check(lowerBound(nums, 6) == 4); // where 6 would be inserted
        check(lowerBound(nums, 99) == nums.length); // past the end: not present
        check(minEatingSpeed(new int[] {3, 6, 7, 11}, 8) == 4);
        check(minEatingSpeed(new int[] {30, 11, 23, 4, 20}, 5) == 30);
        System.out.println("ok: firstTrue, lowerBound and minEatingSpeed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

Why this version is hard to get wrong:

high starts one past the last candidate. [low, high) can be empty, and “not found” has a natural answer: high. For an array, that’s len(nums), which is also the correct insert position for a value bigger than everything.
middle is always less than high, because the division rounds down. So high = middle always shrinks the range, and low = middle + 1 always does too. No infinite loops.
The answer never leaves [low, high]. predicate(middle) true means middle might be the first true, so keep it. False means the first true is after middle, so skip it.

Every variant becomes a choice of predicate:

You want	`predicate(index)`
First index with `nums[index] >= target` (lower bound, insert position)	`nums[index] >= target`
First index with `nums[index] > target` (upper bound)	`nums[index] > target`
Last index with `nums[index] <= target`	upper bound minus 1
Does `target` exist?	lower bound `index`, then check `index < len(nums) and nums[index] == target`
Smallest speed that finishes in time	`hours(speed) <= hour_limit`

The standard libraries ship this too: bisect_left in Python, sort.Search in Go (which is exactly first_true), Arrays.binarySearch in Java and Array.BinarySearch in C#. One warning: with duplicates, Java’s and C#’s versions return some matching index, not the first. Know that before you use them for first-occurrence problems.

Search on the answer

The Koko solution generalizes into a recipe:

What are you minimizing or maximizing? A speed, a capacity, a number of days.
What’s the range? The smallest value that could possibly work and the largest one that surely does. For Koko, 1 to the largest pile.
Write predicate(guess): given a guess, is it feasible? Usually a greedy loop in O(n).
Check that predicate is monotonic: if a guess works, does every bigger guess work? If not, binary search is wrong.

The total cost is O(n log R), where R is the size of the range. Capacity to ship packages, split array largest sum and minimum days to make bouquets all follow this recipe exactly.

Rotated arrays

Rotate [1, 2, 3, 4, 5], and you get [4, 5, 1, 2, 3]. Split it anywhere, and at least one half is still sorted. To find the minimum, compare nums[middle] with nums[high]. If nums[middle] is bigger, the drop (and the minimum) is to the right of middle. Otherwise, it’s at middle or to its left. That’s first_true with predicate(index) = nums[index] <= nums[-1]. It’s false on the left part, and true on the right.

Say this out loud

Checking one speed is easy and it’s monotonic: if a speed works, every faster one does too. So I’ll binary search on the speed, from 1 to the largest pile. That’s O(n log m).

Interview questions

Interviewer asksWhy does your loop use low < high and not low <= high?

Because the range is half-open, [low, high). When low == high, it’s empty, and low is the answer. The low <= high form goes with a closed range [low, high] and high = middle - 1. Both work. The bugs come from mixing them. Pick one form, and always use it.

Interviewer asksFind the first and last position of a target in a sorted array in O(log n).

Two binary searches. First is the lower bound of target: the first index with nums[index] >= target. Last is the lower bound of target + 1, minus one. If the first index is past the end, or doesn’t hold the target, return [-1, -1]. Don’t find one copy and then scan outward. With many duplicates, that’s O(n).

Interviewer asksKoko: why is the upper bound the largest pile and not something bigger?

At a speed equal to the largest pile, every pile takes exactly one hour. So she needs as many hours as there are piles, and the problem guarantees hour_limit is at least that. Any faster speed still takes one hour per pile, so it can’t do better. The answer is never above the largest pile.

Practice

10 problems on LeetCode: 3 easy, 6 medium, 1 hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

Use it when the input is sorted, when O(log n) is required, or when the question is “the smallest or largest X that works”, and checking an X is easy.
One template: first true over [low, high). Set high = middle when true, and low = middle + 1 when not. Return low.
Every variant is a different predicate: lower bound, upper bound, existence, feasibility.
Cost: O(log n) on arrays, O(n log R) on answers.
Watch for: overflow in low + high, mixing half-open and closed ranges, and library functions that return any match rather than the first.