Binary Search Algorithm: How It Works, the Famous Bug, and Interview Patterns

You have a sorted list of one million numbers. Find the number 482,317.

The slow way: start at index 0, check each one. Worst case you read the whole thing. O(n). Fine if you enjoy suffering.

The fast way: look at the middle element. Too big? Target is on the left. Too small? Target is on the right. That one comparison just eliminated half the list. Repeat. You'll find it in at most 20 steps.

That's binary search. It shows up in more interviews than almost any other topic, and it hides an overflow bug that sat unnoticed in Java's standard library for nine years before anyone caught it.

The Core Intuition

Binary search works on any sorted collection. Sorted is the prerequisite. Non-negotiable. Without it, "the middle element is too small" tells you nothing about where to look next.

With it, you can: if the middle element is smaller than your target, everything to its left is also smaller, so you throw away the entire left half.

That one insight is the whole algorithm. Everything else is just bookkeeping.

Think of a physical dictionary. You want "python." You don't start at "aardvark." You open to the middle. Land on "mongoose." Every word left of "mongoose" is alphabetically before it, so you toss the first half and open to the middle of the second. A few more folds and you're there.

A Step-by-Step Example

Here's a sorted array. Target: find 7.

index:  0   1   2   3   4   5   6   7   8
value: [1,  3,  5,  7,  9, 11, 13, 15, 17]

Step 1. left = 0, right = 8. Midpoint: (0 + 8) // 2 = 4. Value at index 4 is 9. Too big. Move left: right = 3.

Step 2. left = 0, right = 3. Midpoint: (0 + 3) // 2 = 1. Value at index 1 is 3. Too small. Move right: left = 2.

Step 3. left = 2, right = 3. Midpoint: (2 + 3) // 2 = 2. Value at index 2 is 5. Still too small. Move right: left = 3.

Step 4. left = 3, right = 3. Midpoint: 3. Value at index 3 is 7. Found it. Return 3.

Four steps for nine elements. At a billion elements, binary search needs 30.

Binary Search Algorithm Implementation

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

Look at the midpoint calculation: left + (right - left) // 2 instead of (left + right) // 2.

Both produce the same result for normal inputs. But if left and right are both large integers, left + right overflows a 32-bit integer. Suddenly your midpoint is negative. Your search goes sideways in a way that's nearly impossible to reproduce on a laptop.

This exact bug lived in Java's standard library binary search for nine years before Joshua Bloch caught it in 2006. The safe form costs exactly nothing to write.

Time Complexity: O(log n)

Each iteration cuts the search space in half. Start with n elements. After one step: n/2. After two: n/4. After k steps: n/2^k.

The loop terminates when the search space hits size 1, which takes at most log₂(n) steps. That gives O(log n) time.

Array size	Max comparisons
10	4
1,000	10
1,000,000	20
1,000,000,000	30

Doubling the input adds exactly one more step. A billion-element array and binary search still finishes in thirty comparisons. That's why it's everywhere.

For more on why O(log n) appears across so many algorithms, not just binary search, see O(log n) Time Complexity Is Not a Coincidence.

Space Complexity: O(1)

The iterative version uses two integer variables no matter how large the array. That's O(1).

A recursive version allocates a new stack frame on each call. Maximum depth is log₂(n), so recursive binary search costs O(log n) space. Prefer iterative. It's simpler to reason about, and you won't accidentally hit a stack limit searching a 10-million-element array.

Where the Bugs Hide

Binary search is the algorithm everyone thinks they can write until they actually sit down and write it. The bug rate in practice is surprisingly high, and it's almost always one of three decisions made inconsistently:

Loop condition: left <= right or left < right?
Pointer movement: left = mid + 1 or left = mid?
Initial right: len(nums) - 1 or len(nums)?

Each combination can be made to work. The bugs come from mixing them. The safest mental model is an invariant: at every point in the loop, "if the target exists, it must be somewhere in [left, right]."

With the inclusive-bounds version ([0, len-1], while left <= right):

When nums[mid] is too small, set left = mid + 1. You've ruled out mid and everything left of it.
When nums[mid] is too big, set right = mid - 1. You've ruled out mid and everything right of it.
Never leave mid in the range after checking it. That's how infinite loops happen.

The loop exits when left > right, meaning the range is empty. If you haven't returned yet, the target isn't there.

The Java stdlib after Joshua Bloch found the nine-year overflow bug in (left + right) / 2.

For a deep dive on invariant-based reasoning including the rotated array variant, see Binary Search: One Invariant to Rule the Search Space. For where subtle mistakes actually appear, Your Binary Search Has an Off-by-One Bug walks through them case by case.

How Binary Search Shows Up in Interviews

You'll see binary search in three distinct forms in coding interviews. Recognizing the form is often harder than writing the code. This is where people who've "done the binary search LeetCode problem" get surprised.

Form 1: Direct Search

Find a target in a sorted array. Canonical. LeetCode 704. Most engineers can write this without thinking.

Form 2: Search in a Modified Sorted Structure

The array is still sorted underneath, but something has been done to it:

Rotated sorted array (LeetCode 33): An array like [4, 5, 6, 7, 0, 1, 2]. One half is always cleanly sorted; the other contains the rotation point. Figure out which half is clean and whether your target falls there.
Find first and last position (LeetCode 34): Duplicates exist and you need the leftmost or rightmost index. Instead of returning when you find the target, record it and keep searching in one direction.
Find minimum in rotated array (LeetCode 153): No target. You're searching for a structural property instead.

The code structure looks like standard binary search. The trick is figuring out which half to eliminate.

Form 3: Binary Search on the Answer

This is the most powerful form, and the one most people don't see coming the first time.

There's no explicit sorted array. Instead, there's a numeric answer in a range [low, high] and a function that tells you whether a candidate answer is feasible. The condition that makes this work: feasibility must be monotone. If a ship capacity of X is enough to deliver all packages, then X+1 is also enough. That monotone property means you can binary search the answer space itself.

Classic examples: find the minimum speed to eat all bananas before the guards return (LeetCode 875), or the minimum ship capacity to deliver all packages in D days (LeetCode 1011).

The signal for this form: the problem asks for a minimum or maximum value, there's an obvious yes/no feasibility test, and the test is monotone. When you see that shape, stop reaching for DP.

Every engineer, the night before the interview that has Form 3 on it.

For a full treatment of this form, see Binary Search on the Answer: Your DP Instinct Is Wrong.

The Variants You Need Cold

Two implementation variants come up often enough to have memorized:

Find leftmost occurrence. When duplicates exist and you want the first index where nums[i] == target:

def find_left(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1  # keep searching left
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

Find insertion point. Where would target go to keep sorted order? When the loop exits, left holds the answer. This is exactly what Python's bisect.bisect_left(a, x) returns: the index of the first element greater than or equal to x.

Once binary search clicks, you start seeing it everywhere: database indexes, version control bisect commands, even how a sorted contacts list loads faster than an unsorted one.

SpaceComplexity runs voice-based DSA mock interviews that test binary search across all three forms, with rubric-based feedback on your approach, edge case handling, and how well you explain your reasoning under pressure. You can write binary search in your sleep. Explaining the invariant out loud while someone watches is a different skill.