Skip to content

Binary Search

Lesson 5 of 7 in Core Patterns · 35 min · Beginner

Halve the search space with every question.

Introduction

I'm thinking of a number from 1 to 100. You can ask yes/no questions like "Is it more than 50?". How few questions do you need to be sure of my number?

The slow way is to ask "Is it 1? Is it 2? Is it 3?" and keep going. If I picked 100, that takes 100 questions.

Now ask "Is it more than 50?" and hear "yes". One question just crossed out 1 through 50. You never have to think about them again.

Lesson overview

This lesson will show you how to:

  • Explain why halving the range takes only about log₂ n steps.
  • Trace lo, hi and mid through a sorted array until you find the target.
  • Spot "minimum value that works" questions that can be binary searched.
  • Choose between closed [lo, hi] and half-open [lo, hi) boundary loops.
  • Avoid the midpoint overflow bug by writing lo + (hi - lo) / 2.

The picture

nums205182123164235386567728lohimidlocheck the middlethis half is goneArray nums with 9 slots: 2, 5, 8, 12, 16, 23, 38, 56, 72. Pointers: lo at index 5; hi at index 8; mid at index 6. Window from index 5 to 8. Marked: index 0 discarded; index 1 discarded; index 2 discarded; index 3 discarded; index 4 discarded; index 6 compare.

Mental model

To find "monkey" in a paper dictionary you don't start at page one. You open it in the middle and land on "M", then see that "monkey" comes later, so the whole front half of the book is out.

Open the middle of what's left, and again, and again. Each peek removes half of the pages, which is why even a huge dictionary takes only a few peeks.

Look at the middle. Because the list is sorted, that one look tells you which half can't hold your target, so throw that half away.

Words to know

sorted
The numbers go from smallest to largest, left to right. Binary search only works when this is true.
lo
The left edge of the range where the target could still be.
hi
The right edge of that range. Everything outside lo and hi has been ruled out.
mid
The index in the middle of lo and hi. It is the one cell you look at each round.
invariant
The promise that stays true every round: if the target is in the array, it is somewhere between lo and hi.
lower bound
The first position whose value is at least the target. It is also where the target would be inserted to keep the list sorted.
monotonic
A yes/no answer that flips only once, like no, no, no, yes, yes, yes. That single flip is what lets you search for it by halving.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: The data is sorted (or you can sort it once) and you need to find a value, or the spot where it belongs.
  • Yes: The problem asks for the minimum or maximum value that works: the smallest speed, the least capacity, the largest size.
  • Yes: You can test one candidate answer quickly, and the test is monotonic: if 5 works, then 6, 7 and 8 work too.
  • Yes: The statement asks for O(log n), or n is so big that looking at everything is too slow.

Not this when

  • No: The data is unsorted and you only need one lookup: a plain scan (or a hash map for many lookups) costs less than sorting first.
  • No: The yes/no test flips more than once: if 5 works, 6 fails and 7 works, one peek can't tell you which half to drop.
  • No: The data is in a linked list: you can't jump to the middle in one step, so every halving costs a walk.

Which pattern fits?

  1. Which pattern? 1 of 5

    Given a sorted array of distinct integers and a target, return the index of the target, or -1 if it isn't there. It must run in O(log n).

  2. Which pattern? 2 of 5

    Koko has n piles of bananas and h hours. Each hour she eats from one pile at speed k. Find the smallest k that lets her finish all the piles in h hours.

  3. Which pattern? 3 of 5

    Given an unsorted array, return the indices of the two numbers that add up to a target.

  4. Which pattern? 4 of 5

    Given a sorted array, find two numbers anywhere in it that add up to a target.

  5. Which pattern? 5 of 5

    Versions 1 to n of a product were shipped, and every version after the first bad one is also bad. Find the first bad version with as few checks as possible.

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1lo = 0, hi = n − 1
  2. while lo <= hi:
  3. 2mid = lo + (hi − lo) / 2
  4. 3if nums[mid] == target:
  5. 6return mid
  6. 3else if nums[mid] < target:
  7. 4lo = mid + 1 (drop the left half)
  8. else:
  9. 5hi = mid − 1 (drop the right half)
  10. 6return −1

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
Time · O(log n)Space · O(1)
  • Each round throws away half of the range, so n numbers need at most about log₂ n rounds. 1,000 numbers take 10 looks and a million take 20.
  • Write the middle as lo + (hi − lo) / 2. The shorter (lo + hi) / 2 can overflow a 32-bit int in Java and C++ when both are large. Both forms give the same answer otherwise.
  • Off-by-one bugs live in two places: the loop test and the moves. With an inclusive range [lo, hi] the loop is lo <= hi and the moves are mid + 1 and mid − 1, because mid has already been checked.
  • To find a boundary instead of a value (first position ≥ target, smallest speed that works), use the half-open range [lo, hi): loop while lo < hi, set hi = mid when mid might be the answer and lo = mid + 1 when it can't.
  • The array has to be sorted first. If it isn't, sorting costs O(n log n), which only pays off when you search many times.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Given a sorted array of integers nums and an integer target, return the index of target in nums, or -1 if it is not there. Your solution must run in O(log n).

Input

nums = [-1,0,3,5,9,12], target = 9

Output

4

Approach

  1. The array is sorted, so one comparison with the middle can rule out half of it.
  2. lo = 0, hi = 5, so mid = 2 and nums[2] = 3. That is smaller than 9, so drop the left half: lo = 3.
  3. Now lo = 3, hi = 5, so mid = 4 and nums[4] = 9. That is the target, so return 4.
  4. If lo ever passes hi, every position has been ruled out, so return -1.
def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
Time · O(log n)Space · O(1)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. You compare nums[mid] with the target in a sorted array and nums[mid] is smaller. What now?
  2. About how many looks does binary search need, at most, to search 1,000 sorted numbers?
  3. Why write mid = lo + (hi − lo) / 2 instead of (lo + hi) / 2?
  4. In the "first position ≥ target" loop, why is it hi = mid and not hi = mid − 1 when nums[mid] ≥ target?
  5. Which of these is a good fit for "binary search on the answer"?

Question 1 of 5

You compare nums[mid] with the target in a sorted array and nums[mid] is smaller. What now?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve First Bad Version (opens in a new tab) (LeetCode, easy)

    Hint: The checks read good, good, bad, bad: the first-true shape. Keep mid when it is bad, because it could be the first one.

  2. Solve Sqrt(x) (opens in a new tab) (LeetCode, easy)

    Hint: You are searching the numbers 0 to x for the biggest m with m * m <= x. Compare with m <= x / m to dodge overflow.

  3. Solve Find First and Last Position of Element in Sorted Array (opens in a new tab) (LeetCode, medium)

    Hint: Run the first-position search twice: once for the first index with a value ≥ target, once for the first index with a value > target.

  4. Solve Find Minimum in Rotated Sorted Array (opens in a new tab) (LeetCode, medium)

    Hint: Compare nums[mid] with the last element. That one comparison tells you whether the drop (the minimum) is on the left or the right of mid.

  5. Solve Search in Rotated Sorted Array (opens in a new tab) (LeetCode, medium)

    Hint: At any mid, at least one half is still properly sorted. Check whether the target falls inside that sorted half, and keep that half or drop it.

  6. Solve Capacity To Ship Packages Within D Days (opens in a new tab) (LeetCode, medium)

    Hint: Binary search on the answer: try a capacity, simulate loading the days, and ask whether it fits. The smallest capacity can't be less than the heaviest package.

  7. Solve Search a 2D Matrix (opens in a new tab) (LeetCode, medium)

    Hint: If you read the rows one after another the matrix is one sorted list. Turn a middle index into a row and column with division and remainder.

  8. Solve Median of Two Sorted Arrays (opens in a new tab) (LeetCode, hard)

    Hint: Don't merge. Binary search how many elements the shorter array gives to the left half, until both left-side maxima are at most both right-side minima.

Additional resources