Binary Search Explained for Beginners: The Invariant Nobody Taught Me

The first time binary search cost me a job, I was 22 minutes into a phone screen with Datadog. I had sent 219 applications over four months and gotten 7 screens. This was screen number 5. The problem was tagged Easy. I wrote a working solution in about ninety seconds, the interviewer said "nice, can you make it return where the target would go if it's not there," and I sat there moving lo and hi around like I was defusing something. Four minutes of silence. Rejection email the next morning.

Here's the thing that made it worse: I had studied this. Every write-up of binary search explained for beginners that I found that week handed me the same six lines of code and the same sentence — sorted array, cut it in half, you'll have it in five minutes. And that sentence is not wrong. It's just missing the part that decides whether you survive the follow-up question.

The advice, and the part of it that's true

The standard advice goes: binary search is the easy pattern, learn it first, it's six lines.

The true part is real. Six lines is about right. The idea genuinely is one sentence long. If you're picking a pattern to start with, this is a reasonable place to start — it shows up at Snowflake, Oracle, Cisco, JPMorgan, Datadog, and thirty-plus other companies, and it shows up often.

The part that breaks down is the word "easy." What people mean when they say binary search is easy is that the idea is easy. The idea is easy. The boundary bookkeeping is where half of us — including me, on a Tuesday morning, on a call I'd waited eight months for — fall apart. Off-by-one errors live here. They live here permanently, and they don't care that you understood the concept.

So this piece is not going to hand you six lines. It's going to hand you the one idea that makes the six lines derivable, so that when someone changes the question on you, you're reasoning instead of guessing.

What the problem is actually asking

Plain English version: you're given a list of numbers that's already sorted from smallest to largest, and a number you're looking for. Return the position (the index) where that number lives. If it isn't in the list, return -1.

That's it. That's the whole problem.

The trap is in the wording, and it's a quiet one. The problem statement says "sorted" the way it says "array" — like it's describing furniture. It reads as background detail. It isn't background detail. "Sorted" is the entire problem. It's the interviewer telling you what tool to reach for, and most people read straight past it.

Here's what sorted actually buys you. I'm going to use one list for this entire piece:

index:  0   1   2   3   4   5    6    7
nums: [-9, -3,  0,  4,  7, 11,  15,  22]

Say you're looking for 15. You peek at index 3 and see 4. Because the list is sorted, you now know something enormous: every value at index 0, 1, 2, and 3 is at most 4. Not "probably." Guaranteed. So 15 cannot be hiding in the left half. One peek eliminated four of eight positions.

In an unsorted list, seeing 4 at index 3 tells you exactly one thing: index 3 isn't your answer. Sorted turns one comparison into information about a whole region. That's the trade.

The obvious answer, and where it stops working

The instinct — and it's a fine instinct, it's the one I had — is to walk the list from the front:

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

This is correct. Let me say that clearly, because a lot of write-ups skip it: this passes. On the standard version of this problem, where the array holds up to about 10,000 numbers, a linear scan runs in microseconds. Nobody's stopwatch goes off.

So where does it break?

It breaks on scale, and it breaks on the follow-up. Scale first. Linear scan is O(n) — worst case, you touch every element. Binary search is O(log n) — every step throws away half of what's left.

A billion entries. Thirty comparisons. That's not a small optimization, that's a different category of thing, and it's why this pattern is in every database index and every query planner at a company like Snowflake.

But the honest answer about interviews is the second one. Nobody rejects you for the linear scan working. They reject you the way I got rejected: the interviewer says "can you do better," you say "binary search," you write six memorized lines, and then they change one detail — return the insertion point, return the first occurrence — and the memorized lines don't stretch. That's the actual failure mode. That's what happened at minute 22.

The reframe: the answer is always inside [lo, hi]

Here's the single idea. Read it slowly, because everything else falls out of it.

You keep two markers, lo and hi. They mark off a stretch of the list. And you make yourself one promise:

If the target is anywhere in this list at all, it is somewhere between lo and hi, inclusive.

That promise is called an invariant — a thing that's true before every step and still true after every step. Your only job on each step is to shrink the stretch without ever breaking the promise.

At the start, the promise is free. lo = 0, hi = 7, the whole list. Obviously the target is in there, if it's anywhere.

Now one step. Look at the middle element, nums[mid]. Three cases:

• nums[mid] == target — found it, return mid.
• nums[mid] < target — the middle is too small. Since the list is sorted, everything from lo through mid is also too small. All of it is ruled out. The new promise-keeping range starts at mid + 1.
• nums[mid] > target — the middle is too big, and so is everything from mid through hi. New range ends at mid - 1.

Notice the + 1 and the - 1. They're not decoration. You checked mid yourself and it wasn't the answer, so mid is ruled out, so it must not be in the next range. Every boundary bug in this pattern comes from being sloppy about that one sentence.

Let's do target = 15 by hand.

Step 1. lo = 0, hi = 7. Middle index is 3, nums[3] = 4. Too small. Ruling out 0 through 3. → lo = 4.

Step 2. lo = 4, hi = 7. Middle index is 5, nums[5] = 11. Too small. Ruling out 4 through 5. → lo = 6.

Step 3. lo = 6, hi = 7. Middle index is 6, nums[6] = 15. Found. Return 6.

Eight elements, three comparisons. That's log₂(8).

The solution, line by line

def search(nums, target):
    lo, hi = 0, len(nums) - 1   # the answer, if it exists, is in [lo, hi]

    while lo <= hi:             # a range of one element is still a real range
        mid = lo + (hi - lo) // 2

        if nums[mid] == target:
            return mid          # found it
        elif nums[mid] < target:
            lo = mid + 1        # mid is too small AND checked -> exclude it
        else:
            hi = mid - 1        # mid is too big AND checked -> exclude it

    return -1                   # range went empty; it was never here

lo, hi = 0, len(nums) - 1. Both ends are positions you still have to check. hi is the last valid index, not the length. Setting hi = len(nums) is a different (also valid) style with different update rules — mixing the two is the number one source of pain.

while lo <= hi. Not <. When lo == hi your range holds exactly one element, and that element hasn't been looked at yet. Using < would walk out the door without checking it, and you'd get a wrong answer on single-element cases — which is exactly the test case interviewers reach for.

mid = lo + (hi - lo) // 2. Covered below.

The three branches. Return, or shrink from the left, or shrink from the right. Each shrink moves a boundary past mid, which is what guarantees the range gets strictly smaller every single pass. That's your termination proof.

return -1. When lo passes hi, the range is empty. The promise said the target would be inside the range. The range has nothing in it. So the target was never in the list.

Watch the empty case actually happen. target = 5:

• lo=0, hi=7, mid 3, nums[3]=4 < 5 → lo=4
• lo=4, hi=7, mid 5, nums[5]=11 > 5 → hi=4
• lo=4, hi=4, mid 4, nums[4]=7 > 5 → hi=3
• lo=4 > hi=3 → loop exits → -1

The range narrowed to nothing and the loop ended on its own. Nothing special-cased.

Time: O(log n). Space: O(1). Two integer variables, no matter how big the list gets.

Why mid = lo + (hi - lo) // 2

In Python, (lo + hi) // 2 gives the same answer and Python integers never overflow, so you can write it and nothing bad happens.

In Java, C++, C#, or Go, lo + hi on a large array can exceed the maximum value a 32-bit int holds, and the sum silently wraps around to a negative number. Your midpoint becomes a negative index. This bug lived inside Java's own standard library for nine years before anyone caught it.

lo + (hi - lo) // 2 computes the distance between the markers first, halves that, and steps forward from lo. The distance is never bigger than the array, so nothing can overflow. Same result, no landmine.

Write it this way every time. Not because your Python needs it, but because the habit means you've already thought about it when someone asks — and at Oracle or JPMorgan, someone asks.

The ways people get this wrong

Mixing while lo < hi with lo <= hi update rules. These are two different templates with two different invariants. lo <= hi with hi = len - 1 means both ends are candidates. lo < hi with hi = len means hi is one past the end. Pick one. Learn it cold. Don't reconstruct from memory mid-interview and end up with a hybrid that's subtly wrong.

Setting hi = mid or lo = mid when you already checked mid. This is the classic infinite loop. If the range is [4, 5], mid computes to 4, and you set lo = mid, then lo is still 4, hi is still 5, and nothing changed. The loop spins forever. Every update must exclude a checked mid.

Computing (lo + hi) / 2 in an overflow-prone language. See above. It reads fine and works fine until the array is large, and then it doesn't.

Only ever practicing exact match. This is the one that got me. Interviews rarely stop at "is it here." They ask for the first occurrence in a list with duplicates, or the last one, or where the value would be inserted. Those variants keep the same invariant and change what happens when you find a match — instead of returning, you record the index and keep shrinking toward the side you want. If you memorized six lines, you have nothing to adapt. If you understand the promise about [lo, hi], you have everything.

The honest version of the rule

The advice said: binary search is easy, it's six lines, learn it in five minutes.

Here's what I'd write instead, after everything: binary search is one easy idea wrapped in a boundary condition that punishes memorization. The idea takes five minutes. The boundaries take an afternoon of writing it out by hand, tracing single-element arrays, and being able to say out loud what your lo and hi are promising you. That afternoon is not you being slow. That afternoon is the actual work, and nobody flagged it as work, which is why so many of us walk in thinking we've got this one covered.

I don't know what I would have said at minute 22 if I'd known the invariant. Probably something like "my range is [lo, hi], and I want the leftmost position where the value is at least the target, so when I find a match I'll record it and keep pushing hi left." That's not a memorized line. That's a sentence you can derive at a whiteboard with someone watching, which is the only kind of knowledge that holds up under pressure.

The four minutes of silence weren't a knowledge gap. They were the sound of a memorized answer meeting a question it hadn't been memorized for.