Binary Search Coding Interview: Defend Your Boundary

Binary search is the shortest algorithm that reliably exposes whether a candidate is reasoning or reciting. The code is five lines. The question underneath it is: can you say what your loop is doing, why it stops, and why the answer cannot escape? That is what a binary search coding interview is really testing. This guide is about that decision — choosing a boundary you can defend, stating it before you type, and holding it steady when the interviewer pushes back.

Why a binary search coding interview trips up strong candidates

Most candidates have written binary search before. That is exactly why it is a useful interview probe. Because everyone has seen it, the interviewer can skip the "do you know this algorithm" question and go straight to "why does your version work?"

Off-by-one errors are rarely carelessness. They are the visible symptom of an unstated invariant. If you never decided whether hi points at a real element or one past the end, your update rules will disagree with each other somewhere, and the bug will show up at the boundary — the empty range, the single element, the target sitting at index 0.

Treat the interview as a conversation about correctness rather than a typing test. A strong answer has a recognisable shape:

1. Say what the search space is.
2. Say what stays true about it on every iteration.
3. Write the loop so that claim is visibly preserved.
4. Say why it terminates and why the answer cannot be discarded.

If you can narrate that shape, the exact code almost writes itself. If you cannot, you are guessing, and interviewers can tell.

Step 1: Name the search space before you write any code

Before touching the keyboard, answer one question: what does my range represent?

There are three common answers, and they lead to different code:

• Indices into an array. You are searching positions, and you compare a[mid] to a target.
• A range of values. The bounds are numbers, not positions — useful when the answer is a quantity rather than a location.
• A range of candidate answers to a yes/no question. Each candidate can be tested, and the test flips from false to true exactly once.

Once you have chosen, state whether your bounds are inclusive or exclusive, and keep that choice for the whole solution. "I'll keep lo inclusive and hi exclusive, so the live range is [lo, hi)" is a sentence worth saying out loud. It costs three seconds and prevents most boundary bugs.

Then explain why the space shrinks. Every iteration must strictly reduce the number of candidates, or the loop may never end. That single sentence — "each branch discards at least one element, so the range gets smaller every time" — is the seed of your termination argument later.

Worked example: target in a sorted array of distinct integers

Say this before coding: "The array is sorted ascending and contains distinct integers. I'm looking for the index of target, or -1 if it is absent. I'll use a half-open range [lo, hi), starting at [0, n). The invariant is that if target exists, its index is inside [lo, hi)."

That is enough setup. The loop is now a formality rather than a memory test.

Step 2: State your invariant in one sentence

An invariant is the claim that stays true before and after every iteration. It is not decoration. It is the thing that tells you which half to throw away.

For the array search above, the invariant is:

If target is in the array, its index is always inside [lo, hi).

Now the decision stops being guesswork. If a[mid] < target, then target cannot be at any index at or below mid, because the array is sorted. So the invariant survives only if you set lo = mid + 1. If a[mid] > target, the answer cannot be at or above mid, so hi = mid. You are not memorising which side gets the +1; you are deriving it.

Two conventions, both correct

The closed interval [lo, hi] and the half-open interval [lo, hi) are both correct. They differ only in what hi means and in the loop condition that matches.

Pick one and stay in it. The failure mode is mixing them: initialising hi = n - 1 (closed) but writing lo < hi (half-open) and then wondering why the last element is never checked.

Step 3: Write the loop so the invariant is obvious

With the invariant fixed, the loop has three jobs: compute a midpoint, compare, and update in a way that preserves the claim.

Midpoint. In most languages, mid = (lo + hi) // 2 is fine for ordinary inputs but can overflow in fixed-width integer types when both bounds are large. mid = lo + (hi - lo) // 2 avoids that. Say which one you are using and why. In Python, integers are arbitrary precision, so the simpler form is safe — mention that if it is relevant to the language you were asked to use.

Updates that match the invariant. With [lo, hi) and the claim "the answer is inside the range":

• If a[mid] == target, return mid.
• If a[mid] < target, the answer is strictly right of mid, so lo = mid + 1.
• If a[mid] > target, the answer is at or left of mid, so hi = mid.

Every branch either returns or shrinks the range. Nothing is left ambiguous.

Loop condition. It must match the interval type. while lo < hi for half-open, while lo <= hi for closed. If you find yourself unsure, ask: what would make the range empty under my convention? That is your exit condition.

Names. lo, hi, and mid are fine because they are conventional. But if your range means something else — say, a capacity — name it low_capacity and high_capacity. The interviewer should be able to follow your code without interrupting, and descriptive names do a lot of that work.

Step 4: Prove termination and correctness out loud

This is the part interviewers remember, and it takes under a minute if you have practised it.

Termination. Argue that the interval strictly shrinks. In the half-open version, every iteration either returns or moves lo up past mid or moves hi down to mid. Since mid is always strictly inside [lo, hi), the new range is strictly smaller. A strictly decreasing sequence of non-negative integers must reach zero, so the loop ends.

Correctness. Argue that the answer is never discarded. At the start, the invariant holds: the whole array is the range. Each update is justified by sortedness, so the invariant holds again. If the loop exits without finding the target, the range is empty, and an empty range contains no index — so the target is genuinely absent, and -1 is the right answer.

Post-loop meaning. Be explicit. In the half-open version, when the loop ends, lo == hi, and that value is the insertion point: the index where the target would go if you inserted it. That is a useful thing to say, because it shows you understand what your variables mean after the loop, not just inside it.

A compact script you can adapt:

"The range shrinks every iteration, so it terminates. The invariant guarantees the answer is never thrown away, so if we exit empty, the target isn't there. At exit, lo is the insertion point."

Three sentences. That is the whole proof at interview granularity.

Step 5: Handle the edge cases interviewers actually probe

Interviewers rarely ask about the happy path. They ask about the boundaries, because that is where unstated assumptions surface. Walk through these out loud before you are asked:

• Empty input. n = 0 gives [0, 0), which is already empty. The loop does not run and you return -1. Say this; it shows your initialisation handles it for free.
• Single element. [0, 1) runs once. Check that your update rules leave an empty range in both the match and no-match cases.
• Target smaller than everything. Every comparison sends hi down until the range is empty. No index is ever wrongly returned.
• Target larger than everything. Symmetrically, lo climbs to n and the loop exits.
• Duplicate values. Plain binary search finds a matching index, not the first or last. If the question asks for a boundary, you need a different predicate: search for the first index where a[i] >= target, then check whether that element equals the target. Say clearly that the problem has changed, and that the invariant now describes a boundary rather than an exact match.
• Rotated or unsorted input. Binary search needs sortedness. Before coding, say how you would detect the problem: check whether the array is sorted, or ask whether the rotation is known. Do not silently assume order you have not verified.

If you had one minute at a whiteboard, test in this order: empty array, single element, target at index 0, target at the last index, target absent. Those five cases catch nearly every boundary bug.

Binary search beyond 'find a value': searching on the answer

A large family of interview problems does not search an array at all. It searches a range of possible answers. The structure is the same; only the search space changes.

You can use binary search whenever you have a yes/no question about a candidate answer, and the answer flips from no to yes exactly once as the candidate grows. That single flip is what makes halving valid.

Worked example: smallest capacity to ship packages within a deadline

You have package weights in order and a number of days. You must ship them in the given order, and you want the smallest daily capacity that finishes within the deadline.

• The search space is a range of capacities, not indices. The lower bound is the heaviest single package; the upper bound is the sum of all weights.
• The predicate is: "with capacity c, can we ship everything within d days?" It is monotonic — a bigger capacity never needs more days.
• Binary search over capacities, calling the predicate at each midpoint, finds the smallest c that works.

Notice what changed and what did not. The midpoint arithmetic, the shrink argument, and the termination proof are identical. What changed is the meaning of the bounds and the cost of each comparison.

How to spot it in the problem statement

Look for phrasing like "smallest maximum", "minimum capacity", "least time", "largest value such that", or any question where you could check a candidate answer with a simple loop. If checking a candidate is easy and the property is monotonic, the intended solution is usually binary search on the answer.

Talking about time and space complexity without reciting

"O(log n)" is the expected answer, but it is not the interesting one. Explain the halving: each iteration removes half the remaining candidates, so the number of iterations is the number of times you can halve n before reaching one. That is the log. The argument is more convincing than the symbol.

Then separate two costs that candidates often blur:

• The cost of the search itself. The number of iterations, multiplied by the cost of one comparison. For array indices, a comparison is constant time, giving O(log n).
• The cost of the predicate. When you search on an answer, each check may scan the whole input. If a predicate costs O(n) and you call it O(log n) times, the total is O(n log n). Say this explicitly, because it is a common follow-up question.

Space is usually O(1) for the iterative version. The recursive version uses O(log n) stack frames, which is worth mentioning if you choose it.

Finally, tie the discussion to the constraints you were given. If n is small, a linear scan may be simpler and fast enough. Sorting plus binary search costs O(n log n) up front, which only pays off if you search the same data many times. If you are searching once, a single pass is often the better answer — and saying so shows judgement rather than reflex.

Recursive or iterative?

Both are acceptable. Iterative is usually the safer default in an interview: no stack depth to discuss, and the boundary updates are right there on the page. Recursion can be clearer when the problem is naturally expressed that way, but be ready to state the recursion depth and the extra space it costs.

How to rehearse binary search reasoning before the interview

Knowing the argument and being able to deliver it under mild pressure are different skills. Practise the second one.

• Narrate, don't just solve. Work through a problem out loud, saying the search space, the invariant, and the termination argument. If you skip a justification, stop and add it.
• Record yourself. Solve one problem on video, then listen back. You will hear exactly where you waved at a boundary instead of explaining it.
• Flip the convention. Re-solve the same problem with a closed interval instead of a half-open one. If it feels like starting over, your understanding was tied to the template rather than the reasoning.
• Practise being interrupted. The real interview will not let you finish a thought in silence. Get comfortable with someone cutting in mid-explanation and asking "why mid + 1?" — and answering without losing your place.
• Rehearse the one-minute proof. Termination, correctness, post-loop meaning. Say it until it is smooth.

For a related angle on talking through solutions without freezing, see Python Interview Questions: Concepts and Trade-Offs. You can also read more on the Blog.

The takeaway: binary search is not a template to reproduce. It is a small proof you write in code. Decide what your range means, say what stays true about it, let that claim choose your updates, and explain why the range must shrink. Do that and the boundaries stop being a memory test — they become the part of the interview you are most confident about.

Frequently asked questions

Should I use inclusive or exclusive bounds in a binary search interview?

Either is correct as long as you apply it consistently. A closed interval [lo, hi] uses while lo <= hi and is empty when lo > hi. A half-open interval [lo, hi) uses while lo < hi and is empty when lo == hi. Choose one, say which you chose out loud, and make sure your initialisation, loop condition and update rules all match that choice. Most boundary bugs come from mixing the two.

What should I say if the interviewer asks why my binary search terminates?

Argue that the range strictly shrinks on every iteration. Each branch either returns or moves one bound past the midpoint, so the number of candidates decreases each time. Because the count of remaining candidates is a non-negative whole number that drops every iteration, it cannot keep dropping forever. Keep it to two or three sentences.

How do I handle binary search when the array has duplicate values?

Plain binary search finds some matching index, not necessarily the first or last. If the question asks for a boundary, change the predicate: search for the first index where the value is greater than or equal to the target, then check whether that element equals the target. State clearly that the problem has changed and that your invariant now describes a boundary rather than an exact match.

Is it acceptable to write binary search recursively in an interview?

Yes, both versions are acceptable. Iterative is usually the safer default because there is no stack depth to discuss and the boundary updates are visible on the page. If you go recursive, be ready to state the recursion depth and the extra space it costs, which is logarithmic in the number of iterations.

How do I recognise a 'binary search on the answer' problem?

Look for phrasing like smallest maximum, minimum capacity, least time, or largest value such that something holds. The tell is that you can check a candidate answer with a simple loop, and the check flips from false to true exactly once as the candidate grows. When both are true, binary search over the range of answers is usually the intended solution.

What is the most common off-by-one mistake in binary search, and how do I avoid it?

The most common mistake is mixing interval conventions — for example initialising hi = n - 1 but writing the loop condition for a half-open range, so the last element is never examined. Avoid it by deciding your convention first, writing it down as a comment, and checking that your initialisation, loop condition and update rules all agree with it before you trace through the empty and single-element cases.

Practise explaining your reasoning out loud in a mock interview session.