Binary search interview mistakes and how to avoid them

In this article

1. Before you start
2. Why interviewers ask this
3. Binary search from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page belongs to the coding interview patterns and practice guide, and it assumes only that you can read a short loop of code.

Why interviewers ask this

A binary search bug costs points because the code looks right on the example and fails on a boundary. The algorithm is short, so an interviewer can watch every decision: the bounds, the midpoint, the loop condition and the return value.

A weak answer writes a remembered template and cannot say why each line is there. A strong answer states the invariant first, writes the loop to match it, and tests an empty array, a single element and a missing value. A Staff-level answer adds the language details: integer width, what the library call returns when the value is missing, and what it does with duplicates.

The topic is old and well studied. Bloch (2006) reported an overflow bug in the Java standard library version, a fair reminder that familiar code still deserves a test. Sorting first and then reasoning about boundaries is also the move behind merge intervals, so the same care transfers.

Binary search from first principles

Invariant

An invariant is a statement about the current search range that is true before the loop starts and after every pass, such as "everything left of low is smaller than the target". Writing it down lets you check each line of the loop against it, which is how you catch a wrong bound before running anything.

Half-open range

A half-open range is a span of positions that includes its low end and excludes its high end, written [low, high), so a high bound equal to the array length covers the whole array and an empty range has low equal to high. One loop condition, low less than high, then handles the empty array and the last element without a special case.

Insertion point

An insertion point is the index where a missing value would have to be placed to keep a sorted array sorted. Library searches return it, or a number built from it, when the value is absent, so it tells you where the search ended even when it found nothing.

Integer overflow

Integer overflow is the error that happens when a fixed-width integer calculation produces a result above the largest value the type can store or below the smallest. In Java the result wraps around to a negative number, and in C signed overflow is undefined behavior. It matters here because adding two valid array indexes can exceed that limit.

In plain words

Binary search is a method that finds a value in sorted data by comparing the target with the middle element and discarding the half that cannot contain it. A linear scan checks every element, so its work grows in step with the size. Binary search halves the range each time, so its work grows like O(log n).

Think of guessing a number someone chose between one and a hundred. Each guess earns "higher" or "lower", and you guess the middle of what is left. The analogy breaks in one place. A person stops when told "correct", but code also needs a clear answer for "no such number" and for several equal numbers.

In one precise sentence, binary search keeps a range that must contain the target if the target is present, and shrinks it until the target is found or the range is empty. Every mistake below is a broken promise about that range.

Step 1: Check the input and pick one bounds convention

A binary search needs a sorted array and one bounds convention chosen before any code is written. Sorted input is a precondition, so an unsorted array gives an undefined result. Java's Arrays documentation says the range must be sorted and that the results are undefined if it is not. In an illustrative unsorted array [5, 1, 9, 3, 7], the value 3 sits at index 3, yet the standard search reports it missing.¹

Then choose the convention. A half-open range [low, high) starts with high equal to the array length, loops while low < high, and sets high = mid. A closed range [low, high] starts with high equal to the length minus one, loops while low <= high, and sets high = mid - 1. Either works. Mixing them is the mistake.

The bounds convention is chosen first, because it fixes the loop condition and the updates. You now have a range that must contain the target if it is present.

Step 2: Compute the midpoint without overflow

The midpoint is computed as low plus half the gap, which cannot overflow. The tempting form, (low + high) / 2, adds two valid indexes first. Bloch (2006) explains that it fails when the sum of low and high is greater than the largest Java int, 2,147,483,647. The sum overflows to a negative value, and the value stays negative when divided by two.

In Java that throws ArrayIndexOutOfBoundsException, and in C it gives an out-of-bounds index with unpredictable results. The post says the version he wrote for the Java standard library had the same bug, that it can appear for arrays of about a billion elements or more, and that it sat in widely used code for about nine years.

Two safe forms are low + (high - low) / 2 and, in Java, (low + high) >>> 1, an unsigned shift. Python integers grow as needed, so the overflow does not occur in plain Python, although fixed-width integer arrays such as NumPy's can still overflow; say which language you mean. Bloch, recalling Bentley's lecture: "The key lesson was to carefully consider the invariants in your programs."

Step 3: Compare and shrink the range

Each comparison discards half the range, and the discarded half never contains the target. If the middle value is too small, everything at or left of the middle is too small, so low moves to mid + 1. If it is too large, high moves left of the middle.

The common failure is an update that fails to shrink the range. With a floor midpoint, setting low = mid leaves the range unchanged whenever the middle equals low, which happens when two elements remain. The loop then runs forever. In an illustrative run on [1, 3] with target 3, that version was still at the same bounds after 10 steps, the cap placed on the demonstration.¹

The rule is short. After every update, either the middle is removed from the range or the other bound has moved. Input: a range and one comparison. Output: a strictly smaller range that still holds the target if the target is present.

Step 4: Stop when the range is empty and return a clear result

The loop ends when the range is empty, and the return value says found or not found. The loop condition must match the convention from Step 1: low <= high for closed bounds, low < high for half-open. Closed bounds with low < high quit with one element left, so on the illustrative array [5] a search for 5 reports it missing.¹ Bounds and condition mismatches like this are the classic off-by-one error.

The return value needs the same care. Java's Arrays.binarySearch returns the index if the key is found, and otherwise minus the insertion point minus one, per the Java 6 documentation. On {10, 20, 30}, the key 25 returns −3, the key 5 returns −1 and the key 40 returns −4.¹ Test result < 0, because −1 only means the insertion point was zero.

Python's bisect module returns an insertion point and never reports "missing", and it only calls __lt__. Check i < len(a) and a[i] == x yourself.

1 · Bounds2 · Midpoint3 · Shrink4 · Stop and returnReplay

Step-by-step description

1. Pick one convention and check sorted input.
2. Low plus half the gap cannot overflow.
3. Discard the half without the target.
4. Empty range, clear found or missing result.

• The bounds convention is chosen first, because it fixes the loop condition and the updates.
• The midpoint is computed as low plus half the gap, which cannot overflow.
• Each comparison discards half the range, and the discarded half never contains the target.
• The loop ends when the range is empty, and the return value says found or not found.

Worked example

The numbers below come from one script that runs small inputs through correct and broken versions of the loop.

Take low 1,500,000,000 and high 2,000,000,000, both valid indexes in an array of that size. Their sum is 3,500,000,000, which exceeds the largest int of 2,147,483,647 from Bloch (2006). In 32-bit arithmetic it wraps to −794,967,296, and halving keeps it negative at −397,483,648.¹ The safe form gives 1,500,000,000 plus 250,000,000, which is 1,750,000,000, and the unsigned shift gives the same value.¹

Counting each probe (loop pass) as one comparison, a sorted array of 1,000,000 elements needs at most 20 comparisons. An array of 1,073,741,824 elements needs at most 31 comparisons.¹

Text description of the diagram

• A sorted array of 1,000,000 elements needs at most 20 comparisons.
• An array of 1,073,741,824 elements needs at most 31 comparisons.

The version below follows every rule at once. It uses a half-open range, a safe midpoint, an update that always shrinks the range, and a return value that is always an insertion point.

def lower_bound(a, target):
    lo, hi = 0, len(a)              # half-open range [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2   # cannot overflow
        if a[mid] < target:
            lo = mid + 1            # mid and everything left of it is too small
        else:
            hi = mid                # mid may be the answer, so keep it
    return lo                       # first index whose value is >= target

a, x = [1, 2, 4, 4, 4, 8], 4        # example input
i = lower_bound(a, x)
found = i < len(a) and a[i] == x

The lower bound is the index of the first element that is not less than the target. On [1, 2, 4, 4, 4, 8] with target 4 it returns 2, which matches bisect_left, and the same search for the first element above 4 returns 5, which matches bisect_right, so the count of 4s is 3.¹ That is how you get the first or last duplicate on purpose, since the Java documentation does not say which duplicate its search finds.

Trade-offs and edge cases

Each mistake has a symptom that shows up in a test and a one-line fix. Sorted input is a precondition, so an unsorted array gives an undefined result.

Text description of the diagram

• Each mistake has a symptom that shows up in a test and a one-line fix.
• Sorted input is a precondition, so an unsorted array gives an undefined result.

Duplicates change what "found" means. A plain equality search returns some matching index, while a lower-bound search returns the first. State which one the problem needs before you write the loop.

Library calls trade control for safety. Python's bisect_left and bisect_right already have the boundaries right, and the Python interview questions page covers when to reach for them. In an interview, say you would use the library in production and still be ready to write the loop by hand.

Binary search also works on an answer, not just an array. If a yes/no question flips from no to yes exactly once as a number grows, such as the smallest capacity that finishes a job in time, you can search that number. The same mistakes apply, with the yes/no test in place of the comparison.

It is not always the right tool. For unsorted data you will search once, a linear scan beats sorting first. For exact membership on unsorted data, a hash map is the usual alternative, as in subarray sum equals k. Picking the few smallest items without fully sorting uses a heap or quickselect instead, as in k closest points to origin.

Reasoning is not enough. Bloch's post says to consider the invariants, and it also shows a version that was correct on paper and failed on real integers, so you still test.

How to answer it in an interview

The spoken structure: state the invariant, write the loop to match it, name the midpoint and return-value traps, then say how you would test it.

Common mistakes

• "I'll just write mid = (low + high) / 2." (wrong) That overflows in fixed-width languages once the sum passes the largest integer. (right) "In Java I'll use low + (high - low) / 2."
• "If the result is not −1, the value was found." (wrong) Java returns a negative number built from the insertion point. (right) "A negative result means not found, and I decode the insertion point from it."
• "The library gives me the first duplicate." (wrong) The Java documentation does not say which match is returned. (right) "I search the lower bound when I need the first one."
• "The array is sorted, so I skip the check." (wrong) An unsorted input gives an undefined result. (right) "I state the sorted precondition and ask if it holds."
• "It passed the example, so it is done." (wrong) Boundary bugs hide on tiny and huge inputs. (right) "I test empty, one element, two elements, missing values and duplicates."

Follow-up questions

How do you find the first occurrence of a value with binary search?

Search the lower bound: keep hi = mid whenever a[mid] >= target, then check that lo < len(a) and a[lo] == target. On [1, 2, 4, 4, 4, 8] with target 4, that returns index 2.¹

Why is adding low and high to find the midpoint a bug?

The sum of two valid indexes can exceed the largest integer the type holds, and then it wraps to a negative number. Writing low + (high - low) / 2 never adds the two large values together.

What does Java's binarySearch return when the key is missing?

It returns minus the insertion point minus one, so the result is always negative for a missing key. For the key 25 in {10, 20, 30} that is −3.¹

Does Python's bisect tell you whether a value is present?

No. It returns an insertion point, and it only compares with less-than, so you check i < len(a) and a[i] == x afterwards.

How do you test a binary search?

Try an empty array, one element, two elements, a value before the first, after the last and between two elements, plus duplicates. Compare the result with a linear scan on random sorted arrays, and use very large indexes to catch overflow.

Can you use binary search on something that is not an array?

Yes, whenever a yes/no test flips exactly once as a number grows, so you can search the number itself. Problems built on a moving window, such as longest substring without repeating characters, use a different pattern.

Sources

1. Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken — Google Research Blog (Joshua Bloch), 2 Jun 2006
2. bisect - Array bisection algorithm — Python Software Foundation (Python 3 documentation), 26 Oct 2026
3. java.util.Arrays (Java 25 API documentation) — Oracle, 26 Oct 2026
4. java.util.Arrays (Java 6 API documentation, binarySearch return value) — Oracle, 26 Oct 2026