Binary Search: The Core Idea

I think of a whole number between 1 and 1,000. You guess, and I answer only "higher" or "lower". The best first guess is 500. Whatever I answer, 500 numbers are gone in one question. Guess the middle of what is left, again and again, and you always win in at most 10 guesses.

That game is binary search. The idea is not "a sorted array". The idea is one question that rules out a whole half. A sorted array is the common way to get such a question, but it is not the only way, and the problems that separate strong candidates are the ones where nothing looks sorted at all.

Binary search gets more time in this course than most patterns for an honest reason: the loop is ten lines long, and most engineers write it with a bug. Interviewers know this and use it on purpose.

The intuition: one question, half the candidates gone

Count what halving does. Start with 1,000,000 candidates:

Twenty steps. A linear scan of the same range needs 500,000 on average. The number of steps is how many times you can halve n before one candidate is left, which is log₂ n. Doubling the input adds one step, not twice the steps.

Read the chart for its shape, not its values. The linear line climbs off the top while the binary-search line stays almost flat. That is what "logarithmic" means in practice: a thousand times more data costs about ten more comparisons.

How to recognise it

The constraints talk too. If n ≤ 10⁵ and there are also 10⁵ queries, a linear scan per query is 10¹⁰ steps, far too slow, while log₂ 10⁵ ≈ 17 steps per query is instant. If the statement says "your solution must run in O(log n)", the interviewer is telling you the pattern.

The strongest signal is a word like minimum, smallest, first or earliest attached to a condition that is easy to check but hard to compute directly. "Is speed 7 fast enough?" is easy to check. "What is the slowest speed that is fast enough?" is hard to compute. That gap is where binary search lives.

How it works: a monotonic test and an invariant

Binary search needs one thing: a yes/no question you can ask about any candidate, whose answers, laid out in order, look like this:

candidate:  0   1   2   3   4   5   6   7answer:     no  no  no  no  yes yes yes yes

This is called a monotonic test: once the answer turns to yes, it never turns back to no. For a sorted array and the question "is nums[i] >= target?", the answers are no up to some index and yes after it. That is all "sorted" buys you. Sorting is one way to get a monotonic test; it is not a requirement.

With a monotonic test, you look at the middle candidate. If the answer there is yes, every candidate to its right is also yes, so the first yes is at mid or to its left. If the answer is no, every candidate to its left is also no, so the first yes is strictly to the right. Either way, half the range is gone.

What keeps this correct is an invariant: a sentence that is true before the loop starts and after every step. For binary search it is always some form of:

If the answer exists, it is inside [left, right].

Every update must keep that sentence true, and every step must make the range strictly smaller. If both hold, the loop ends, and when it ends the answer is wherever the invariant says it is. Write the invariant as a comment before you write the loop. It takes a few seconds, and it turns the loop condition and the updates into things you derive instead of things you remember.

Two forms, and where each is used

The same two templates cover every problem in this section. What changes from problem to problem is what you search over and what test you ask:

The templates

Template 1, the exact match. Memorise this one exactly.

1def binary_search(nums: list[int], target: int) -> int:2    """Return an index of target in sorted nums, or -1 if it is absent."""3    left, right = 0, len(nums) - 1           # inclusive: nums[left..right] is still live4    # invariant: if target is in nums, it is inside nums[left..right]5    while left <= right:                     # left == right is one unchecked element6        mid = left + (right - left) // 27        if nums[mid] == target:8            return mid9        if nums[mid] < target:10            left = mid + 1                   # mid and everything left of it are too small11        else:12            right = mid - 1                  # mid and everything right of it are too big13    return -1                                # the range is empty: target is absent

Four decisions, each with a reason:

1. right = len(nums) - 1: the range is inclusive. Both nums[left] and nums[right] are still candidates. Every other line follows from this choice.
2. while left <= right, not left < right. When left == right, one element is still unchecked. With < you skip it: searching [5] for 5 would return -1.
3. mid = left + (right - left) // 2. It is the same number as (left + right) // 2. In Java, C++ or Go with 32-bit integers, left + right can pass about 2.1 billion and turn negative. right - left never overflows. Python integers cannot overflow, but write it this way anyway: the habit transfers, and interviewers from those languages look for it.
4. mid + 1 and mid - 1, never plain mid. nums[mid] has been compared and is not the target, so it must leave the range. If you wrote left = mid when mid == left, the range would not shrink and the loop would never end.

Template 2, the boundary search. It finds the first candidate where a monotonic test says yes.

1from typing import Callable234def first_true(lo: int, hi: int, ok: Callable[[int], bool]) -> int:5    """Smallest x in [lo, hi) with ok(x) True, or hi if there is none.67    ok must be monotonic: False ... False True ... True.8    """9    left, right = lo, hi                     # half-open: the answer is in [left, right]10    while left < right:                      # stop when one candidate remains11        mid = left + (right - left) // 212        if ok(mid):13            right = mid                      # mid works; it might be the first that does14        else:15            left = mid + 1                   # mid fails; the answer is strictly after it16    return left171819def lower_bound(nums: list[int], target: int) -> int:20    """First index whose value is >= target, or len(nums) if none is."""21    return first_true(0, len(nums), lambda i: nums[i] >= target)

Line by line:

• right = hi, one past the last candidate. "None of them works" is a legal answer, and it is reported as hi. For lower_bound that is len(nums): the target is bigger than everything and would be inserted at the end.
• while left < right. The loop runs while two or more positions are possible. When left == right, one position is left and it is the answer, so there is nothing to check.
• right = mid when ok(mid) is true. mid works, but something to its left might also work. So mid stays in the range as a candidate.
• left = mid + 1 when ok(mid) is false. Because the test is monotonic, mid and everything before it fail.
• The loop always ends. mid rounds down, so mid is less than right. right = mid shrinks the range, and left = mid + 1 shrinks it too.

first_true is the most reusable ten lines in this course. First Bad Version — versions 1..n, find the first bad one, given an is_bad(v) check — is first_true(1, n + 1, is_bad) and nothing more. Koko Eating Bananas, later in this section, is the same call with a different test.

The two templates must never be mixed. Pick a column and write all four rows from it:

Python ships the boundary search: bisect.bisect_left(nums, target) is lower_bound, and bisect.bisect_right finds the first value strictly greater. Mention them, but interviewers almost always want the loop written by hand.

Complexity

• Time: O(log n). Each step removes at least half of the range, so after k steps at most n / 2ᵏ candidates are left. That reaches one after about log₂ n steps.
• Space: O(1). Three integers. A recursive version uses O(log n) stack frames for no benefit, so write it as a loop.
• On a range of answers: O(log(range) × cost of one test). If testing one answer takes a pass over n items and the range is 10⁹ wide, that is about 30 × n.

Where it goes wrong

1. The loop that never ends. This is the most common failure, and it hangs instead of returning a wrong answer.

1while left < right:2    mid = left + (right - left) // 2      # rounds DOWN3    if condition(mid):4        left = mid                        # when mid == left, nothing changes5    else:6        right = mid - 1

With left = 3 and right = 4, mid is 3. If the condition holds, left stays 3 and the loop repeats forever. The rule: if a branch sets left = mid, round mid up. You need that when you search for the last candidate that works, such as the integer square root, the largest x with x × x ≤ n:

1def last_true(lo: int, hi: int, ok: Callable[[int], bool]) -> int:2    """Largest x in [lo, hi] with ok(x) True. Assumes ok(lo) is True.34    ok must be monotonic the other way: True ... True False ... False.5    """6    left, right = lo, hi7    while left < right:8        mid = left + (right - left + 1) // 2   # round UP: one branch sets left = mid9        if ok(mid):10            left = mid                       # mid works; the last one is here or later11        else:12            right = mid - 1                  # mid fails; the answer is before it13    return left141516def integer_sqrt(n: int) -> int:17    """Largest x with x * x <= n, for n >= 0."""18    return last_true(0, n, lambda x: x * x <= n)

Rounding up makes mid greater than left, so left = mid always moves forward. integer_sqrt(10**12) returns 1000000 after about 40 tests.

2. The loop test does not match the bounds. Inclusive bounds with while left < right skip the last single element: [5] searched for 5 returns -1. Half-open bounds with while left <= right run once too often and read nums[len(nums)].

3. The wrong starting bound. A boundary search that starts with right = len(nums) - 1 can never return len(nums). The bug only shows when the target is bigger than every value, which is exactly the case people forget to test.

4. Trusting a boundary without checking it. lower_bound returns a position, whether or not the target is there. On [1, 5, 9] with target 3 it returns 1, and nums[1] is 5. Check i < len(nums) and nums[i] == target before you call it found.

5. A test that is not monotonic. If the answers can go no, yes, no, binary search returns nonsense without any error. Before coding, say out loud why the test cannot switch back.