Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Introduction to Binary Search

Editorial

Halving the search

I'm thinking of a number from 1 to 1,000,000. You guess, and I say "higher" or "lower". If you guess 1, 2, 3 and so on, you could need 1,000,000 guesses. Guess the middle instead, 500,000, and whatever I answer rules out half the numbers at once. Keep guessing the middle of what's left, and you'll never need more than 20 guesses. A billion numbers would take 30.

That's binary search: in a sorted list, look at the middle, decide which half the answer is in, and throw the other half away. Each look halves what's left, so it takes about log₂ n looks: O(log n).

The idea is simple. Writing it correctly is famously not: Knuth noted that the first binary search was published in 1946 and the first one without bugs only in 1962. This lesson gives you one loop, and one rule for it, that removes the off-by-one bugs.

Binary search on a sorted row of 16 numbers. The first look at the middle rules out 8 of them, the second rules out 4 of the 8 left, the third 2 of the 4, and the fourth leaves the one number that can be the answer. Each look halves what's left, so 16 items need at most 4 looks and a million need 20: O(log n).

Searching for a value

The search keeps a range [lo, hi] that holds the target if it's in the array at all. Look at the middle, mid. If nums[mid] is the target, you're done. If it's smaller, the target can only be to the right, so move lo past mid. If it's bigger, move hi before mid. When the range is empty, the target isn't there.

On [-1, 0, 3, 5, 9, 12], looking for 9:

Binary search for a value — The shaded range still holds the target if it's there. Each step looks at mid and throws half the range away.

int search(const vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;     // the target, if it's here, is in [lo, hi]
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;           // the middle, without overflow
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;   // it can only be to the right of mid
        else hi = mid - 1;                      // it can only be to the left of mid
    }
    return -1;                                  // [lo, hi] is empty: it isn't here
}

def search(nums, target):
    lo, hi = 0, len(nums) - 1                   # the target, if it's here, is in [lo, hi]
    while lo <= hi:
        mid = (lo + hi) // 2                    # the middle
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1                        # it can only be to the right of mid
        else:
            hi = mid - 1                        # it can only be to the left of mid
    return -1                                   # [lo, hi] is empty: it isn't here

static int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;           // the target, if it's here, is in [lo, hi]
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;           // the middle, without overflow
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;   // it can only be to the right of mid
        else hi = mid - 1;                      // it can only be to the left of mid
    }
    return -1;                                  // [lo, hi] is empty: it isn't here
}

function search(nums, target) {
    let lo = 0, hi = nums.length - 1;           // the target, if it's here, is in [lo, hi]
    while (lo <= hi) {
        const mid = lo + Math.floor((hi - lo) / 2);   // the middle
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) lo = mid + 1;   // it can only be to the right of mid
        else hi = mid - 1;                      // it can only be to the left of mid
    }
    return -1;                                  // [lo, hi] is empty: it isn't here
}

Each prints 4, -1, 0 and 1 for 9 in [-1, 0, 3, 5, 9, 12], 2 in [-1, 0, 3, 5, 9, 12], 5 in [5] and 4 in [2, 4].

mid = lo + (hi - lo) / 2 is the same middle as (lo + hi) / 2, but it can't overflow: in Java and C++, lo + hi can be bigger than the largest int (see the mistakes below).

Every binary search is a yes/no question

Most binary searches don't look for one value. They look for a boundary: the first index where something becomes true. In [1, 3, 3, 5, 5, 5, 8, 9, 12], ask "is nums[i] at least 5?" at every index, and the answers are no, no, no, yes, yes, yes, yes, yes, yes (the figure below draws them).

On a sorted array the answers run no, no, …, yes, yes: they flip once. The first yes, index 3, is the lower bound of 5. Binary search finds where the flip is, and two rules make it correct:

  1. The answer stays in [lo, hi]. Start with lo = 0 and hi = n, where hi = n stands for "no yes anywhere".
  2. The range shrinks every step.

If the question says yes at mid, the first yes is mid or something to its left: hi = mid (not mid - 1, which could drop the answer). If it says no, the first yes is to the right: lo = mid + 1. Because mid rounds down, it's always below hi, so both updates shrink the range. When lo == hi, that's the answer.

The yes/no question nums[i] ≥ 5 on the sorted array 1, 3, 3, 5, 5, 5, 8, 9, 12. The answers are no for the first three values and yes from index 3 on: they flip exactly once. Binary search finds the flip, the first yes at index 3, by keeping it inside the range [lo, hi] and shrinking that range at every step.

Finding the first yes (the lower bound) — The shaded range always holds the first yes. Green means yes at mid; amber means no.

Try it yourself

Here you choose every update. The widget shows mid and the answer to the question there; you pick lo = mid, lo = mid + 1, hi = mid or hi = mid − 1. Keep the answer inside [lo, hi] and make the range shrink. Then try the wrong ones: drop the answer, or pick an update that doesn't shrink the range and watch the loop get stuck. Switch to last ≤ x and change how mid rounds to see why that question needs mid rounded up.

The Boundary Finder: choose every update of a binary search and see when the answer is dropped or the loop gets stuck

Template: the first yes

Here's the loop for the lower bound, the first index with nums[i] >= x:

int lowerBound(const vector<int>& nums, int x) {
    int lo = 0, hi = nums.size();               // the answer is in [lo, hi]; nums.size() means none
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;           // rounds down, so mid < hi
        if (nums[mid] >= x) hi = mid;           // yes: the answer is mid or to its left
        else lo = mid + 1;                      // no: the answer is to the right of mid
    }
    return lo;                                  // lo == hi: the first index with nums[i] >= x
}

def lower_bound(nums, x):
    lo, hi = 0, len(nums)                       # the answer is in [lo, hi]; len(nums) means none
    while lo < hi:
        mid = (lo + hi) // 2                    # rounds down, so mid < hi
        if nums[mid] >= x:
            hi = mid                            # yes: the answer is mid or to its left
        else:
            lo = mid + 1                        # no: the answer is to the right of mid
    return lo                                   # lo == hi: the first index with nums[i] >= x

static int lowerBound(int[] nums, int x) {
    int lo = 0, hi = nums.length;               // the answer is in [lo, hi]; nums.length means none
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;           // rounds down, so mid < hi
        if (nums[mid] >= x) hi = mid;           // yes: the answer is mid or to its left
        else lo = mid + 1;                      // no: the answer is to the right of mid
    }
    return lo;                                  // lo == hi: the first index with nums[i] >= x
}

function lowerBound(nums, x) {
    let lo = 0, hi = nums.length;               // the answer is in [lo, hi]; nums.length means none
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);   // rounds down, so mid < hi
        if (nums[mid] >= x) hi = mid;           // yes: the answer is mid or to its left
        else lo = mid + 1;                      // no: the answer is to the right of mid
    }
    return lo;                                  // lo == hi: the first index with nums[i] >= x
}

Each prints 3, 3, 9 and 0 for x = 5, 4, 13 and 0 in [1, 3, 3, 5, 5, 5, 8, 9, 12]. For x = 13 nothing is big enough, and the answer is 9: the "none" slot past the end. Change the question to nums[mid] > x and the same loop is the upper bound, the first index with a value greater than x.

One loop, many questions

Write the loop once, with the question passed in, and the classic searches are all one call:

def first_yes(lo, hi, yes):
    """The first index in [lo, hi) where yes(i) holds, or hi if there is none."""
    while lo < hi:
        mid = (lo + hi) // 2
        if yes(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


nums = [1, 3, 3, 5, 5, 5, 8, 9, 12]
n = len(nums)
first5 = first_yes(0, n, lambda i: nums[i] >= 5)     # the lower bound of 5: the first 5
after5 = first_yes(0, n, lambda i: nums[i] > 5)      # the upper bound of 5: just past the last 5
print(first5, after5 - 1, after5 - first5)          # the first 5, the last 5, how many 5s
print(first_yes(0, n, lambda i: nums[i] >= 4))       # where 4 would go: the insertion point
print(first_yes(0, n, lambda i: nums[i] > 7) - 1)    # the floor of 7: the last value <= 7
print(first_yes(0, n, lambda i: nums[i] >= 7))       # the ceiling of 7: the first value >= 7

It prints 3 5 3, then 3, 5 and 6:

You wantAsk "first index where…"Answer
the first 5 (lower bound)nums[i] ≥ 5that index, if it holds 5
the last 5nums[i] > 5that index − 1
how many 5sboth of the abovethe difference
where 4 would go (Search Insert Position)nums[i] ≥ 4that index
the floor of 7, the last value ≤ 7nums[i] > 7that index − 1
the ceiling of 7, the first value ≥ 7nums[i] ≥ 7that index

Find First and Last Position of Element in Sorted Array is the first two rows. Random Pick with Weight asks for the first running total that's bigger than a random number: the same loop on a prefix sum array.

The last yes: round mid up

Some questions flip the other way: yes, yes, …, no. The last value ≤ x is one. Now a yes at mid means the answer is mid or to its right, so the update is lo = mid, and a no means hi = mid - 1. One thing changes with it: mid must round up.

def last_at_most(nums, x):
    """The last index with nums[i] <= x, or -1 if there is none."""
    lo, hi = -1, len(nums) - 1                  # the answer is in [lo, hi]; -1 means none
    while lo < hi:
        mid = (lo + hi + 1) // 2                # round UP, because the next line may set lo = mid
        if nums[mid] <= x:
            lo = mid                            # yes: the answer is mid or to its right
        else:
            hi = mid - 1                        # no: the answer is to the left of mid
    return lo

It returns 5, -1 and 8 for x = 5, 0 and 13 in [1, 3, 3, 5, 5, 5, 8, 9, 12]. Here's why the rounding matters. When the range is two slots, say [7, 8], a rounded-down mid is 7, the same as lo. If that's a yes, lo = mid sets lo to 7 again, and nothing moves. Run with mid = (lo + hi) // 2 on x = 9 and a cap of 1,000 rounds, it returns (7, 8, 1000): still at [7, 8] after a thousand rounds. Rounding up makes mid 8, and the range shrinks.

When to use binary search

Clues:

  • A sorted array, and you need a value or a position in O(log n).
  • "first", "last", "smallest index such that", "insert position": a boundary.
  • A yes/no question that flips once as you move along, even with no array: "is this number too big?" in Guess Number Higher or Lower, or "can it be done with x?", which is the lesson Binary Search on the Answer.

Near-misses:

  • Unsorted data: sorting first costs O(n log n), and it loses the original positions.
  • A linked list: reaching the middle takes O(n) steps, so halving saves nothing.
  • A question that flips more than once: halving can throw the answer away. Rotated arrays and peaks still work, for their own reasons, in Binary Search Without a Sorted Array.

Common mistakes

Overflow in the middle. int mid = (lo + hi) / 2;

In Java with lo = 1,500,000,000 and hi = 2,000,000,000, it prints -397483648: lo + hi is bigger than the largest int and wraps around to a negative number. lo + (hi - lo) / 2 prints 1750000000. This bug sat in Java's own library for years. Python's integers don't overflow.

while lo <= hi with hi = mid.

The boundary loop stops at lo == hi. With <= it keeps going, and with lo == hi a yes sets hi = mid, which is hi again. Capped at 1,000 rounds, the lower bound of 5 returns (3, 3, 1000): stuck at [3, 3]. Use < with hi = mid.

Returning the lower bound as if it were the target. return lower_bound(nums, target)

Searching [1, 3, 3, 5, 5, 5, 8, 9, 12] for 4 returns 3, but index 3 holds 5. The lower bound is where 4 would go. Check that the value there is the target, and return -1 if it isn't.

Starting hi at n - 1 when the answer can be "none". lo, hi = 0, len(nums) - 1

The lower bound of 13 in [1, 3, 3, 5, 5, 5, 8, 9, 12] then returns 8, the last index, though nothing there is 13 or more. The answer has to be allowed to be n.

Check yourself

Quiz

1 / 5

Multiple choice

Finding the first index with nums[i] >= x: at mid the answer is yes. Which update keeps every place the answer could be, and nothing else?

Practice problems

From easier to harder:

  1. Binary Search: the value search.
  2. Implement Lower Bound: the first yes.
  3. Implement Upper Bound: the same loop with >.
  4. Search Insert Position: the lower bound, by another name.
  5. Floor & Ceiling in Sorted Array: two questions, one loop.
  6. Guess Number Higher or Lower: the question is an API call.
  7. Find First and Last Position of Element in Sorted Array: lower and upper bound.
  8. Random Pick with Weight: the first running total above a random pick.
  9. Find K Closest Elements: binary search for where the window of k starts.

Next: Binary Search Without a Sorted Array, for rotated arrays, peaks and pairs.