My binary search says 0 isn’t in [4, 5, 6, 7, 0, 1, 2]

DSA · Core
30 min read, about 1 h 30 min with practice

Concept
Asked often: high
Reviewed 2026-11

New to some of the words above? Open a quick recap. Each takes about two minutes.

Quick recapBig-O in two minutes· 2 min

Big-O says how the work grows as the input grows. One loop over n items is O(n): twice the items, twice the work. O(log n) means each step halves what’s left, so twice the items take just one more step: a million items take about 20. The full lesson: My code passed every test, then timed out on the big one.

Quick recapSorted lists in two minutes· 2 min

A sorted list goes from small to big: sorted(nums) makes one, and nums.sort() sorts in place, in O(n log n). In a sorted list, every number to the left of x is at most x, and every number to the right is at least x. That’s what lets one check rule out half. The full lesson: My sort is right, but 50,000 scores take half a minute.

See the problem

The interview task: a sorted list was turned. Some numbers from the front moved to the back, in order, like [4, 5, 6, 7, 0, 1, 2]. Find where a number is, fast.

Binary search is fast on a sorted list. It checks the middle, and throws away the half that can’t hold the target:

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1  # too small: the target can only be to the right
        else:
            hi = mid - 1  # too big: the target can only be to the left
    return -1

For 0, it checks 7: too big, so it keeps the left half. Then 5, then 4, both too big. It says -1. But 0 is right there, at index 4.

“Too big, so it’s to the left” is true only in a sorted list. This one turns after 7: everything to the right of 7 is smaller.

Define the task

Write search(nums, target).

Input: nums, up to 200,000 different whole numbers: a list sorted from small to big, then turned, with some numbers from the front moved to the back, in order. It may not be turned at all, and it may be empty. target is a whole number.
Output: the index of target in nums, or -1 if it isn’t there.
The hard part: the same list is searched again and again. The speed test searches 200,000 numbers 20,000 times, so each search must take about 18 steps, not 200,000.

Example: search([4, 5, 6, 7, 0, 1, 2], 0) is 4. search([4, 5, 6, 7, 0, 1, 2], 3) is -1.

Pause and think

Hints open one at a time:

Hint 1 of 3

The list turns once at most. Cut it anywhere, and the turn is in one half at most: the other half is sorted.

Hint 2 of 3

Compare the number at lo with the one at mid. If it’s smaller or the same, the numbers rise all the way from lo to mid: the left half is sorted. If not, the right half is.

Hint 3 of 3

A sorted half holds just the numbers from its first end to its last. If the target is between them, keep that half. If not, keep the other one. Either way, half goes.

Understand the idea

Binary search halves what’s left. In a sorted list, check the middle. If it’s the target, you’re done. If it’s too small, everything to its left is too small too, so only the right half can hold the target. Each check throws away half: 200,000 numbers take at most 18 checks, since 2¹⁸ is 262,144.

lo and hi mark what’s left. One rule holds at every step: if the target is in the list, it’s between lo and hi. Loop while lo <= hi, since one number left still needs a check. Then move lo = mid + 1 or hi = mid - 1: mid has been checked, so it leaves too.

Watch it on a sorted list. Then try a target that isn’t there.

Binary search

Step 1 of 5. lo and hi start at both ends: if 31 is here, it lies between them.

Speed Ask me first Show as text

1def binary_search(nums: list[int], target: int) -> int:
2    lo, hi = 0, len(nums) - 1
3    while lo <= hi:
4        mid = (lo + hi) // 2
5        if nums[mid] == target:
6            return mid
7        if nums[mid] < target:
8            lo = mid + 1
9        else:
10            hi = mid - 1
11    return -1

A turned list breaks that rule. In [4, 5, 6, 7, 0, 1, 2], 7 is bigger than 0, but 0 is to its right. “Too big” no longer says which side to keep.

But one half is always sorted. A turned list rises, drops once, and rises again. Cut it at mid, and the drop is in one half at most. If nums[lo] <= nums[mid], there’s no drop from lo to mid: the left half is sorted. If not, the drop is there, so the right half is sorted.

A sorted half is easy to check. It holds just the numbers from its first end to its last. So if the target is between those two, it can only be in that half. If not, it can only be in the other one. Either way, half goes, as in plain binary search: about log n checks.

The same halving works on a yes/no question. Say “is build v bad?” is no, no, no, and then yes from some build on. That’s like a sorted list of no’s and yes’s, so binary search finds the first yes. The first practice problem does this.

And on the answer itself. Say you want the smallest van that does every delivery in 8 hours. You can’t list every answer, but you can check one size quickly, and every bigger size works too. So binary search the sizes: check the middle one, and keep the half that holds the smallest size that works. The other two practice problems do this.

Watch it on a turned list. The faded numbers are ruled out, and the highlighted ones are the sorted half. Try the one from the top: 4 5 6 7 0 1 2 and 0.

Binary search on a turned list

Work so far

target	1
checks so far	0

Step 1 of 9. lo and hi start at both ends. If 1 is in the list, it’s between them.

Speed Ask me first Show as text

1def search(nums: list[int], target: int) -> int:
2    lo, hi = 0, len(nums) - 1
3    while lo <= hi:
4        mid = (lo + hi) // 2
5        if nums[mid] == target:
6            return mid
7        if nums[lo] <= nums[mid]:  # the left half is sorted
8            if nums[lo] <= target < nums[mid]:
9                hi = mid - 1
10            else:
11                lo = mid + 1
12        else:  # the right half is sorted
13            if nums[mid] < target <= nums[hi]:
14                lo = mid + 1
15            else:
16                hi = mid - 1
17    return -1

Climb the ladder

All three find 0 at index 4. What changes is how many numbers they check.

The idea: Read the numbers from left to right, and return the index of the target when you meet it.

It doesn’t care whether the list is sorted, turned or mixed up, so it can’t be wrong.

def search(nums: list[int], target: int) -> int:
    for i, x in enumerate(nums):  # check every number, left to right
        if x == target:
            return i
    return -1

Time: O(n)
Space: O(1)
Why: A search for a number that isn’t there reads all n.

Where it breaks: 200,000 numbers, searched 20,000 times. Each search reads up to 200,000 numbers: about 2 billion reads in all. It runs out of time on the speed test.

The idea: First binary search for the turn, the smallest number: if the number at mid is bigger than the one at hi, the turn is to the right of mid. The numbers before the turn are sorted, and so are the ones from it on. Then binary search the side that can hold the target.

The waste in Okay: it checks numbers that can’t be the target. Most of the list is sorted, and a sorted stretch can be halved.

Highlighted lines are new in this rung.

def search(nums: list[int], target: int) -> int:
    # 1. Find the turn: the index of the smallest number.
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the turn is right of mid
        else:
            hi = mid  # mid may be the turn itself
    turn = lo
    # 2. Search the sorted side that can hold the target.
    if turn > 0 and target >= nums[0]:
        lo, hi = 0, turn - 1
    else:
        lo, hi = turn, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Time: O(log n)was O(n)
Space: O(1)
Why: Two binary searches, one after the other: about 2 log n checks, 36 for 200,000 numbers.

What changed from the previous rung

def search(nums: list[int], target: int) -> int:
    for i, x in enumerate(nums):  # check every number, left to right
        if x == target:
            return i
    # 1. Find the turn: the index of the smallest number.
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the turn is right of mid
        else:
            hi = mid  # mid may be the turn itself
    turn = lo
    # 2. Search the sorted side that can hold the target.
    if turn > 0 and target >= nums[0]:
        lo, hi = 0, turn - 1
    else:
        lo, hi = turn, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Where it breaks: it passes every test here. But it’s two searches with different rules: the turn search keeps mid (hi = mid) and loops while lo < hi, and the other drops mid. Each is its own place for an off-by-one, and it checks about twice as many numbers as it needs.

The idea: Check mid. One half is sorted: the left one if the number at lo is at most the one at mid, and the right one if not. If the target is between that half’s ends, keep that half. If not, keep the other one.

The waste in Better: it finds the turn first, though no search needs it. At every mid, one half is sorted already, and that’s enough to pick a half.

Highlighted lines are new in this rung.

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:  # the left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # the right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Time: O(log n)
Space: O(1)
Why: Each round halves what’s left: at most 18 rounds for 200,000 numbers.

What changed from the previous rung

def search(nums: list[int], target: int) -> int:
    # 1. Find the turn: the index of the smallest number.
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the turn is right of mid
        else:
            hi = mid  # mid may be the turn itself
    turn = lo
    # 2. Search the sorted side that can hold the target.
    if turn > 0 and target >= nums[0]:
        lo, hi = 0, turn - 1
    else:
        lo, hi = turn, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
        if nums[lo] <= nums[mid]:  # the left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # the right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

When Best isn’t best: when numbers can repeat. In [1, 1, 1, 2, 1], nums[lo], nums[mid] and nums[hi] are all 1, so neither half is known to be sorted. Then all you can do is drop one number from each end, and the worst case is O(n).

Write it yourself

Now write it in the page. Press Run tests to check your code. Python runs in your browser, so nothing is sent anywhere. Your code is saved in this browser for next time.

Try Okay from the ladder first: it runs out of time on the speed test. Better and Best both pass.

Search a turned list

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: search([4, 5, 6, 7, 0, 1, 2], 0): plain binary search says -1 → 4
Not run yet: search([4, 5, 6, 7, 0, 1, 2], 3) → -1
Not run yet: search([4, 5, 6, 7, 0, 1, 2], 5) → 1
Not run yet: search([1, 2, 3, 4, 5], 4): not turned at all → 3
Not run yet: search([3, 1], 1): the left half is just the 3 → 1
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 200,000 numbers, searched 20,000 times: how many come back right → 20000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Compare

Way	Time	Extra memory	Good	Not so good	Use it when
Okay: check every number	O(n)	O(1)	Works on any list, sorted or not	Reads every number when the target isn’t there	One search in a short list
Better: find the turn, then search	O(log n)	O(1)	Two plain binary searches	Two loops with different rules, and twice the checks	You need the turn anyway, as in “how far was it turned?”
Best: one binary search	O(log n)	O(1)	One loop, about log n checks	Needs the reason one half is always sorted	Always, for this problem

How much work is one search? Each bar is one rung, for a target that isn’t there. Pick a size, or run the race.

One search in n numbers, for a number that isn’t there

OkayCheck every number · O(n)≈ 200,000 steps
BetterFind the turn, then search · O(log n)≈ 36 steps
BestOne binary search · O(log n)≈ 18 steps

At n = 200,000, Okay does about 11,000 times more work than Best.

Every bar does the same number of steps per second, so the race shows which rung finishes first. Turn on Log scale to compare the short bars.

Twice the numbers means twice the steps for Okay, but just one more round for Better and Best: 1,000,000 numbers take Best 20 rounds.

In this page’s Python, the speed test’s 20,000 searches take Okay over a minute, depending on the computer. Better and Best take a fifth of a second or less.

Common mistakes and edge cases

nums[lo] <= nums[mid], with <=. When lo and mid are the same place, the left half is just that one number, and it’s sorted. With <, search([3, 1], 1) looks in the wrong half and says -1.
Leave mid out of the range checks. mid has been checked, so the left test is nums[lo] <= target < nums[mid] and the right test is nums[mid] < target <= nums[hi].
Not turned at all. Then the left half is always sorted, and it’s plain binary search. Test it anyway.
Two loops, two rules: don’t mix them. To find one number, loop while lo <= hi and move lo = mid + 1 or hi = mid - 1. To find the first yes, loop while lo < hi and set hi = mid on a yes, since mid may be the answer. With hi = mid and while lo <= hi, the loop never ends once lo == hi.
(lo + hi) // 2 is fine in Python, whose whole numbers have no size limit. In Java or C++, lo + (hi - lo) / 2 keeps the sum from overflowing.
Repeated numbers. With repeats, nums[lo] == nums[mid] can’t tell which half is sorted. Ask whether numbers can repeat.

Say it in the interview

Questions to ask first

Are all the numbers different?
Can the list be not turned at all, or empty?
Should it return -1 when the target isn’t there?
Is the list searched once, or many times?

A 60-second walkthrough

“Binary search, with one change. I keep lo and hi around the part that can still hold the target. At each mid, if it’s the target, I return it. If not, one half is sorted, since the list turns at most once: if the number at lo is at most the one at mid, it’s the left half, otherwise the right. A sorted half holds just the numbers between its ends. So I check whether the target is between them, and keep that half or the other one. Each round halves what’s left: O(log n) time and O(1) memory.”

Likely follow-ups

Find the smallest number, or how far the list was turned? Binary search for the turn: if nums[mid] > nums[hi], it’s to the right of mid; if not, it’s mid or to its left. Its index is how far the list was turned.
What if numbers can repeat? When nums[lo], nums[mid] and nums[hi] are all the same, move lo and hi in by one each. The worst case becomes O(n), as for [1, 1, 1, 1, 2, 1, 1].
Why not sort it, then binary search? Sorting is O(n log n), slower than one scan, and it moves the numbers, so the indexes change.
A sorted list so long you can’t see its end? Check places 1, 2, 4, 8, … until you pass the target, then binary search the last stretch: O(log k) for a target at place k.

Practice

Three problems, from easy to hard: the first bad build, the smallest van, and a reading plan. The first finds the first yes of a yes/no question. The other two binary search the answer itself. Each has hints, tests you can run here, and its own Okay, Better and Best answers. For each rung, say its Big-O before you open it.

1. The first bad build (easy)

Write first_bad(n, is_bad). Builds are numbered 1 to n, and one of them broke the code: it and every build after it are bad. is_bad(v) says whether build v is bad. Each check runs the tests, which takes minutes, so check as few builds as you can. Build n is always bad.

Example: with n = 5 and builds 4 and 5 bad, first_bad(5, is_bad) is 4.

Hint 1 of 3

The answers to is_bad go no, no, …, then yes, yes, like a sorted list. So binary search for the first yes.

Hint 2 of 3

Keep the first bad build between lo and hi. If mid is bad, the first bad one is mid or before it: hi = mid. If not, it’s after mid: lo = mid + 1.

Hint 3 of 3

Stop when lo == hi: that’s the first bad build. That’s one check a round, so 31 checks for 2 billion builds.

The first bad build

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: first_bad(5, lambda v: v >= 4) → 4
Not run yet: first_bad(5, lambda v: v >= 1) → 1
Not run yet: first_bad(5, lambda v: v >= 5) → 5
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 2 billion builds, and the first bad one is near the end → 1500000000
Not run yet: 2 billion builds, in 32 checks or fewer → 1234

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Show the Okay, Better and Best answers

The idea: Check builds 1, 2, 3, … and return the first bad one.

It finds the first bad build by meeting it, so it can’t miss.

from collections.abc import Callable


def first_bad(n: int, is_bad: Callable[[int], bool]) -> int:
    for v in range(1, n + 1):  # check every build, from the first
        if is_bad(v):
            return v
    return n

Time: O(n)
Space: O(1)
Why: It checks every build up to the first bad one: up to n checks.

Where it breaks: 2 billion builds, with the first bad one near the end: about 1.5 billion checks. It runs out of time on the speed test.

The idea: Binary search. If mid is bad and the build before it is good, mid is the answer. If mid is bad, go left; if it’s good, go right.

The waste in Okay: one check says something about many builds. If build v is good, so is every build before it.

Highlighted lines are new in this rung.

from collections.abc import Callable


def first_bad(n: int, is_bad: Callable[[int], bool]) -> int:
    lo, hi = 1, n
    while lo <= hi:
        mid = (lo + hi) // 2
        if is_bad(mid):
            if mid == 1 or not is_bad(mid - 1):
                return mid  # bad, and the one before it is good
            hi = mid - 1
        else:
            lo = mid + 1
    return n

Time: O(log n)was O(n)
Space: O(1)
Why: About log n rounds, with up to two checks each.

What changed from the previous rung

from collections.abc import Callable


def first_bad(n: int, is_bad: Callable[[int], bool]) -> int:
    for v in range(1, n + 1):  # check every build, from the first
        if is_bad(v):
            return v
    lo, hi = 1, n
    while lo <= hi:
        mid = (lo + hi) // 2
        if is_bad(mid):
            if mid == 1 or not is_bad(mid - 1):
                return mid  # bad, and the one before it is good
            hi = mid - 1
        else:
            lo = mid + 1
    return n

Where it breaks: it’s fast, but at every bad mid it checks mid − 1 too. For 2 billion builds with the first bad one early, that’s 56 checks, and the last test allows 32.

The idea: Keep the first bad build between lo and hi. If mid is bad, hi = mid, since mid may be the first. If not, lo = mid + 1. Stop when lo == hi.

The waste in Better: it checks mid − 1 to see whether mid is the first. Keeping mid in the range answers that at no extra cost, once lo meets hi.

Highlighted lines are new in this rung.

from collections.abc import Callable


def first_bad(n: int, is_bad: Callable[[int], bool]) -> int:
    lo, hi = 1, n  # the first bad build is in lo..hi
    while lo < hi:
        mid = (lo + hi) // 2
        if is_bad(mid):
            hi = mid  # mid may be the first bad one
        else:
            lo = mid + 1  # the first bad one comes after mid
    return lo

Time: O(log n)
Space: O(1)
Why: One check a round, and each round halves what’s left: 31 checks for 2 billion builds.

What changed from the previous rung

from collections.abc import Callable


def first_bad(n: int, is_bad: Callable[[int], bool]) -> int:
    lo, hi = 1, n
    while lo <= hi:
    lo, hi = 1, n  # the first bad build is in lo..hi
    while lo < hi:
        mid = (lo + hi) // 2
        if is_bad(mid):
            if mid == 1 or not is_bad(mid - 1):
                return mid  # bad, and the one before it is good
            hi = mid - 1
            hi = mid  # mid may be the first bad one
        else:
            lo = mid + 1
    return n
            lo = mid + 1  # the first bad one comes after mid
    return lo

When Best isn’t best: when checks can run side by side. With 8 machines, check 8 builds at once and keep a ninth of the range each round: fewer rounds, though more checks.

2. The smallest van (medium)

Write smallest_van(boxes, hours). A van delivers to some stops: boxes[i] boxes go to stop i. Each trip takes an hour, goes to one stop, and carries up to s boxes. Return the smallest s that delivers every box in hours hours or fewer. There’s at least one stop, each gets at least 1 box, and hours is at least the number of stops.

Example: smallest_van([3, 6, 7, 11], 8) is 4. With 4 boxes a trip, the stops take 1, 2, 2 and 3 trips: 8 hours. With 3, they take 10.

Hint 1 of 3

A bigger van never needs more trips. So the sizes go: too small, too small, …, then big enough from some size on. Find the first size that’s big enough.

Hint 2 of 3

Binary search the size, from 1 to the most boxes at one stop. That size takes one trip a stop, so it always works.

Hint 3 of 3

To check a size s, add up each stop’s trips: its boxes divided by s, rounded up, which is (b + s - 1) // s. If they add up to hours or fewer, s works, and so might a smaller size: hi = mid.

The smallest van

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: smallest_van([3, 6, 7, 11], 8) → 4
Not run yet: smallest_van([30, 11, 23, 4, 20], 5): one trip a stop, so the biggest stop → 30
Not run yet: smallest_van([30, 11, 23, 4, 20], 6) → 23
Not run yet: smallest_van([5], 2) → 3
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 10 stops of a billion boxes each, in 20 hours → 500000000
Not run yet: Speed test: one stop of 10 million boxes and 49,999 stops of 1, in 50,999 hours → 10000

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Show the Okay, Better and Best answers

The idea: Try s = 1, 2, 3, … and return the first size whose trips add up to hours or fewer.

It tries the sizes in order, so the first that works is the smallest.

def trips(boxes: list[int], s: int) -> int:
    """Hours for every stop, with s boxes a trip: each stop's boxes / s, rounded up."""
    return sum((b + s - 1) // s for b in boxes)


def smallest_van(boxes: list[int], hours: int) -> int:
    s = 1
    while trips(boxes, s) > hours:  # try every size, from 1 up
        s += 1
    return s

Time: O(n × s)
Space: O(1)
Why: It tries every size up to the answer s, and each try adds up the trips of all n stops.

Where it breaks: 10 stops of a billion boxes, in 20 hours. The answer is 500 million, so it tries 500 million sizes. It runs out of time on the first speed test.

The idea: Each hour moves at most s boxes, so s is at least all the boxes divided by hours, rounded up. Start there, and count up.

The waste in Okay: it tries sizes that can’t work. Every size below the total divided by the hours is too small.

Highlighted lines are new in this rung.

def trips(boxes: list[int], s: int) -> int:
    """Hours for every stop, with s boxes a trip: each stop's boxes / s, rounded up."""
    return sum((b + s - 1) // s for b in boxes)


def smallest_van(boxes: list[int], hours: int) -> int:
    # Each hour moves at most s boxes, so s is at least the total / hours, rounded up.
    s = (sum(boxes) + hours - 1) // hours
    while trips(boxes, s) > hours:
        s += 1
    return s

Time: O(n × s) at worstwas O(n × s)
Space: O(1)
Why: When the stops are about the same size, it starts at the answer or close to it. When one stop is much bigger, it counts up a long way.

What changed from the previous rung

def trips(boxes: list[int], s: int) -> int:
    """Hours for every stop, with s boxes a trip: each stop's boxes / s, rounded up."""
    return sum((b + s - 1) // s for b in boxes)


def smallest_van(boxes: list[int], hours: int) -> int:
    s = 1
    while trips(boxes, s) > hours:  # try every size, from 1 up
    # Each hour moves at most s boxes, so s is at least the total / hours, rounded up.
    s = (sum(boxes) + hours - 1) // hours
    while trips(boxes, s) > hours:
        s += 1
    return s

Where it breaks: one stop of 10 million boxes and 49,999 stops of 1. It starts at 198 and counts up to 10,000, adding up 50,000 stops each time: about 490 million steps. It runs out of time on the second speed test.

The idea: The answer is between 1 and the biggest stop. Check the middle size: if it works, the answer is it or smaller; if not, it’s bigger. Halve until one size is left.

The waste in Better: it checks sizes one at a time, though one check rules out every size on one side of it.

Highlighted lines are new in this rung.

def trips(boxes: list[int], s: int) -> int:
    """Hours for every stop, with s boxes a trip: each stop's boxes / s, rounded up."""
    return sum((b + s - 1) // s for b in boxes)


def smallest_van(boxes: list[int], hours: int) -> int:
    lo, hi = 1, max(boxes)  # max(boxes) takes one trip a stop, so it works
    while lo < hi:
        mid = (lo + hi) // 2
        if trips(boxes, mid) <= hours:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid is too small, and so is every size below it
    return lo

Time: O(n log m)was O(n × s) at worst
Space: O(1)
Why: m is the most boxes at one stop: about 30 checks for a billion, and each adds up n stops.

What changed from the previous rung

def trips(boxes: list[int], s: int) -> int:
    """Hours for every stop, with s boxes a trip: each stop's boxes / s, rounded up."""
    return sum((b + s - 1) // s for b in boxes)


def smallest_van(boxes: list[int], hours: int) -> int:
    # Each hour moves at most s boxes, so s is at least the total / hours, rounded up.
    s = (sum(boxes) + hours - 1) // hours
    while trips(boxes, s) > hours:
        s += 1
    return s
    lo, hi = 1, max(boxes)  # max(boxes) takes one trip a stop, so it works
    while lo < hi:
        mid = (lo + hi) // 2
        if trips(boxes, mid) <= hours:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid is too small, and so is every size below it
    return lo

When Best isn’t best: when a check is slow and the answer is almost always tiny. If it’s usually 1 or 2, trying 1, 2, … finds it in a check or two, where binary search takes about 30.

3. A reading plan (hard)

Write busiest_day(pages, days). A book’s chapters have pages[i] pages each. You read them in order, whole chapters each day, over days days, and you may finish early. Return the fewest pages your busiest day can have. Each chapter has at least 1 page, and days is from 1 to the number of chapters.

Example: busiest_day([7, 2, 5, 10, 8], 2) is 18: read 7, 2 and 5 (14 pages), then 10 and 8 (18).

Hint 1 of 3

Guess a limit: at most L pages a day. Does the book fit in the days? A bigger limit never needs more days, so binary search for the smallest limit that fits.

Hint 2 of 3

To check a limit, fill each day as full as it goes: add chapters until the next one doesn’t fit, then start a new day. Count the days.

Hint 3 of 3

The answer is at least the longest chapter, and at most all the pages in one day. Binary search between those two.

A reading plan

Ctrl + Enter runs

Loads about 6 MB the first time. Best on Wi-Fi.

Not run yet: busiest_day([7, 2, 5, 10, 8], 2) → 18
Not run yet: busiest_day([1, 2, 3, 4, 5], 2) → 9
Not run yet: busiest_day([1, 4, 4], 3): no day can hold less than the longest chapter → 4
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Extra test
Not run yet: Speed test: 36 chapters in 12 days → 190
Not run yet: Speed test: 50,000 chapters in 10 days → 2502500

Extra tests check tricky cases. You see their input only if they fail.

Try your own input

Show the Okay, Better and Best answers

The idea: For today, try stopping after each chapter, and plan the rest the same way with one day fewer. Keep the plan whose busiest day is smallest.

It tries every plan, so it can’t miss the best one.

def busiest_day(pages: list[int], days: int) -> int:
    def plan(start: int, left: int) -> int:
        """The fewest pages on the busiest day, to read pages[start:] in `left` days."""
        rest = sum(pages[start:])
        if left == 1:
            return rest  # one day left: read it all
        most = rest  # reading it all today is one way
        today = 0
        for end in range(start, len(pages) - 1):  # or stop today after chapter `end`
            today += pages[end]
            most = min(most, max(today, plan(end + 1, left - 1)))
        return most

    return plan(0, days)

Time: O(nᵈ)
Space: O(d)
Why: It tries every way to cut n chapters into d days or fewer: for 36 chapters in 12 days, about 700 million calls. Each call is waiting on the one it made, d deep at most.

Where it breaks: 36 chapters in 12 days: about 700 million calls, each adding up the rest of the book. It runs out of time on the first speed test.

The idea: For a limit, fill each day as full as it goes and count the days. Try limits from the longest chapter up, and return the first one that fits.

The waste in Okay: it tries every plan, though one rule settles whether a limit fits: fill each day as full as it goes. Stopping a day early only pushes pages onto the days after it.

Highlighted lines are new in this rung.

def days_needed(pages: list[int], limit: int) -> int:
    """The fewest days to read every chapter in order, with at most `limit` pages a day."""
    count, today = 1, 0
    for p in pages:
        if today + p > limit:  # it doesn't fit: it starts a new day
            count += 1
            today = 0
        today += p
    return count


def busiest_day(pages: list[int], days: int) -> int:
    limit = max(pages)  # the busiest day holds at least the longest chapter
    while days_needed(pages, limit) > days:  # try every limit, from there up
        limit += 1
    return limit

Time: O(n × S)was O(nᵈ)
Space: O(1)was O(d)
Why: S is all the pages. Each check reads every chapter once, and it can try up to S limits.

What changed from the previous rung

def busiest_day(pages: list[int], days: int) -> int:
    def plan(start: int, left: int) -> int:
        """The fewest pages on the busiest day, to read pages[start:] in `left` days."""
        rest = sum(pages[start:])
        if left == 1:
            return rest  # one day left: read it all
        most = rest  # reading it all today is one way
        today = 0
        for end in range(start, len(pages) - 1):  # or stop today after chapter `end`
            today += pages[end]
            most = min(most, max(today, plan(end + 1, left - 1)))
        return most
def days_needed(pages: list[int], limit: int) -> int:
    """The fewest days to read every chapter in order, with at most `limit` pages a day."""
    count, today = 1, 0
    for p in pages:
        if today + p > limit:  # it doesn't fit: it starts a new day
            count += 1
            today = 0
        today += p
    return count

    return plan(0, days)

def busiest_day(pages: list[int], days: int) -> int:
    limit = max(pages)  # the busiest day holds at least the longest chapter
    while days_needed(pages, limit) > days:  # try every limit, from there up
        limit += 1
    return limit

Where it breaks: 50,000 chapters in 10 days. The answer is 2,502,500, so it checks about 2.5 million limits, reading 50,000 chapters for each. It runs out of time on the second speed test.

The idea: The answer is between the longest chapter and all the pages. Check the middle limit: if it fits, the answer is it or smaller; if not, it’s bigger.

The waste in Better: it tries limits one at a time. But a limit that fits rules out every bigger one, and one that doesn’t fit rules out every smaller one.

Highlighted lines are new in this rung.

def days_needed(pages: list[int], limit: int) -> int:
    """The fewest days to read every chapter in order, with at most `limit` pages a day."""
    count, today = 1, 0
    for p in pages:
        if today + p > limit:  # it doesn't fit: it starts a new day
            count += 1
            today = 0
        today += p
    return count


def busiest_day(pages: list[int], days: int) -> int:
    lo, hi = max(pages), sum(pages)  # one day for everything always works
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(pages, mid) <= days:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid is too small, and so is every limit below it
    return lo

Time: O(n log S)was O(n × S)
Space: O(1)
Why: About 25 checks for 25 million pages, each reading every chapter once.

What changed from the previous rung

def days_needed(pages: list[int], limit: int) -> int:
    """The fewest days to read every chapter in order, with at most `limit` pages a day."""
    count, today = 1, 0
    for p in pages:
        if today + p > limit:  # it doesn't fit: it starts a new day
            count += 1
            today = 0
        today += p
    return count


def busiest_day(pages: list[int], days: int) -> int:
    limit = max(pages)  # the busiest day holds at least the longest chapter
    while days_needed(pages, limit) > days:  # try every limit, from there up
        limit += 1
    return limit
    lo, hi = max(pages), sum(pages)  # one day for everything always works
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(pages, mid) <= days:
            hi = mid  # mid works, so the answer is mid or smaller
        else:
            lo = mid + 1  # mid is too small, and so is every limit below it
    return lo

When Best isn’t best: when the chapters can be read in any order. Then filling each day in turn no longer works, and it becomes a much harder problem.

Check yourself

A few quick questions. Ones you miss are remembered, so you can find your weak spots later.

Predict the outputThis is plain binary search on a turned list. What does it print?

nums = [4, 5, 6, 7, 0, 1, 2]
lo, hi = 0, len(nums) - 1
checked = []
while lo <= hi:
    mid = (lo + hi) // 2
    checked.append(nums[mid])
    if nums[mid] == 0:
        break
    if nums[mid] < 0:
        lo = mid + 1
    else:
        hi = mid - 1
print(checked)

[7, 5, 4][7, 1, 0][7, 0][4, 5, 6, 7, 0]

Multiple choiceIn [6, 7, 8, 1, 2, 3, 4, 5], lo is 0 and hi is 7, so mid is 3, and nums[mid] is 1. Which half is sorted?
The left half, from 6 to 1The right half, from 1 to 5Both halvesNeither half

Spot the bugThis should return the first bad build. What's wrong?

def first_bad(n, is_bad):
    lo, hi = 1, n
    while lo <= hi:
        mid = (lo + hi) // 2
        if is_bad(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

It can loop foreverIt returns one build too lateIt can check build 0Nothing

Multiple choiceAt most how many checks does binary search need for 1,000,000 sorted numbers?
201,000500,0001,000,000
Pick the patternA file was uploaded in 1,000 parts, and from some part on, every part is broken. Checking a part takes a minute. How do you find the first broken part fast?
Binary search for the first broken partCheck the parts in order, from the firstPut the parts in a hash mapSlide a window over the parts

Flashcards

Add these to your review deck. Each card comes back a little later every time you get it right.

Cheat sheet

To find one number: loop while lo <= hi, take mid = (lo + hi) // 2, then move lo = mid + 1 or hi = mid - 1. Return -1 after the loop.
To find the first yes: loop while lo < hi, set hi = mid on a yes and lo = mid + 1 on a no. Return lo.
n numbers take at most ⌊log₂ n⌋ + 1 checks: 18 for 200,000, and 31 for 2 billion.
A turned list: at each mid, one half is sorted. nums[lo] <= nums[mid] means it’s the left half.
A sorted half holds just the numbers between its ends: check the target against them.
On the answer: when you can check a guess, and every bigger guess works too, binary search the guesses.
bisect.bisect_left(nums, x) finds where x goes in a sorted list, with a binary search written in C.

Go deeper

Do it yourself: binary search on the DSA visualizer, where you pick each mid, and a turned list.
The basic sorting lesson: sorting once is what makes every later search O(log n).
The Big-O lesson says why log n grows so slowly.
Next on the DSA roadmap: fast and slow pointers.

Can you do these now?

If you’re not sure of any of these, scroll back to that part before moving on.

Keep lo and hi around what can still hold the answer, and drop half of it at every step
Search a sorted list that was turned in O(log n), by finding the half that’s sorted
Find the first yes of a yes/no question that flips once, like the first bad build
Binary search the answer itself, when you can check a guess and every bigger guess works too

Status: Not started

My binary search says 0 isn’t in [4, 5, 6, 7, 0, 1, 2]

See the problem

Define the task

Pause and think

Understand the idea

Climb the ladder

Check every number

Find the turn, then search one side

One binary search, with the sorted half

Write it yourself

Search a turned list

Compare

Common mistakes and edge cases

Say it in the interview

Practice

1. The first bad build (easy)

The first bad build

Check every build

Binary search, checking two builds

Binary search for the first yes

2. The smallest van (medium)

The smallest van

Try every size

Start at the smallest size that could work

Binary search the size

3. A reading plan (hard)

A reading plan

Try every way to split

Try every limit

Binary search the limit

Check yourself

Flashcards

Cheat sheet

Go deeper

Can you do these now?