vizlearn

Write binary search without an off-by-one

Interview QuestionsBy Updated

Keep a half-open range [lo, hi) and the loop writes itself: while lo < hi, lo = mid + 1 or hi = mid. Both branches strictly shrink the range, which is what guarantees termination — and hi = mid with an inclusive hi is the version that hangs.

Overview

The question, and what it is testing

Keep a half-open range [lo, hi) and the loop writes itself: while lo < hi, lo = mid + 1 or hi = mid. Both branches strictly shrink the range, which is what guarantees termination — and hi = mid with an inclusive hi is the version that hangs.

Binary searchCoding problemEasy

Step through it

What to watch

  • The range is [lo, hi): hi is never a candidate.
  • lo = mid + 1 rules mid out; hi = mid keeps it.
  • The loop ends with lo at the insertion point, found or not.

Say this out loud

"I use a half-open range: lo inclusive, hi exclusive, loop while lo is less than hi. If a[mid] is less than the target, lo becomes mid + 1, otherwise hi becomes mid. Both branches shrink the range strictly, so it terminates, and at the end lo is the insertion point - one comparison tells me whether the value is actually there."

Write binary search without an off-by-one

Write binary search. What makes it terminate, and where do the off-by-one errors come from?

Run it

The half-open version, and the inclusive one that stops making progress.

1Python
Output
The invariant, stated as the thing that is true on every iteration.
2Python
Output
The overflow idiom Python does not need, and what you would actually use.
3Python
Output

                

                

                    
The invariant does the work

                    
Binary search is three lines and most people can write a version that usually works. What separates that from a correct one is being able to say what is true at the top of every iteration: if the target is present, it is in [lo, hi).
Everything follows. The loop condition is lo < hi, because an empty range means the answer is not there. When a[mid] < target, mid cannot be the answer, so lo = mid + 1 excludes it. Otherwise mid might be the answer, so hi = mid keeps it in a half-open range. Neither branch can leave the range the same size, which is termination.

                

                

                    
The two combinations that hang

                    
Pair an inclusive hi = len(a) - 1 with hi = mid and you have a loop that can stop making progress: when hi = lo + 1, mid equals lo, and setting hi = mid changes nothing. The editor below runs that version under a step cap so you can see it exhaust its budget rather than hanging the page.
The mirror error is lo = mid instead of lo = mid + 1, which hangs for the same reason from the other side. The rule that avoids both: the branch that keeps mid as a candidate must be the one that moves the exclusive end.

                

                

                    
The overflow line, and why Python does not need it

                    
You will see mid = lo + (hi - lo) // 2 in every C and Java implementation, and the reason is real: lo + hi can exceed the integer width on a large array, a bug that sat in the JDK for nine years.
Python integers are arbitrary precision, so (lo + hi) // 2 is safe here — and the editor prints both forms agreeing at 262 to show it. Knowing why the idiom exists is worth more than using it: it is a good answer to "is there anything else to say about this line?"

                

                

                    
What to use instead

                    
In real Python, bisect. bisect_left(a, x) is exactly this loop, written in C, and it returns the insertion point — which is strictly more useful than a boolean, because it answers "where would it go" as well as "is it there". The next question is entirely about that.
Write the loop when asked to, and say that you would reach for bisect in production. Both halves of that answer are being listened for.

                

                

                    
What to say out loud

                    
I use a half-open range: lo inclusive, hi exclusive, loop while lo is less than hi. If a[mid] is less than the target, lo becomes mid + 1, otherwise hi becomes mid. Both branches shrink the range strictly, so it terminates, and at the end lo is the insertion point - one comparison tells me whether the value is actually there.

                

                

                    
Edge cases to raise

                    
Volunteering these is most of what separates a correct answer from a good one.
The empty array. hi = 0, the loop body never runs, and lo is 0 - which is the correct insertion point. A version starting at len(a) - 1 gets hi = -1 and needs a guard.
Targets outside the range. The answer is 0 or len(a), both of which are valid insertion points and neither of which is a valid index. The final bounds check is what separates them.
Duplicates. The plain loop returns an arbitrary one. If that matters, you want a boundary search, not this.

                

                

                    
The follow-ups interviewers ask

                    
"Write it recursively." Same invariant, and it costs stack depth for no benefit - log n frames rather than two variables. Worth writing if asked, and worth noting that the iterative form is what every library ships.
"What if the array is rotated?" One extra comparison per step to decide which half is sorted, then the same invariant. It is the standard escalation from this question.
"How would you test it?" Every array length from 0 to about 5, and for each one every target including one below the minimum, one above the maximum, and the gaps. That is a few dozen cases and it catches every off-by-one - which is a better answer than any single clever test.

                

                

                    
Common wrong answers

                    
"while lo <= hi with hi = mid." This is the combination that hangs. If hi is inclusive, the branch that keeps mid must be hi = mid - 1.
"Return mid when a[mid] == x." Correct for presence, and it makes the loop unable to answer 'first' or 'last' - which is the next question.
"Use lo + (hi - lo) // 2 because Python can overflow." Python integers cannot overflow. The idiom is right and the reason given is wrong, and interviewers notice the difference.

                

                

                    
Recap in one screen

                    
  • The range is [lo, hi): hi is never a candidate.
  • lo = mid + 1 rules mid out; hi = mid keeps it.
  • The loop ends with lo at the insertion point, found or not.
  • Worth trying: Change hi = mid to hi = mid - 1 in search and look for the value that is now missed. The bug is silent, which is why the invariant matters more than the shape.
  • Worth trying: Return lo instead of -1 on a miss. That is bisect_left, and it is the version most real problems want.

                

            


        

    



How the code works
The half-open version, the inclusive version that stops making progress, and the overflow idiom that Python does not need but every other language does.
How the code works
  1. lo, hi = 0, len(a)hi starts one past the end because it is exclusive. That single choice is what makes the rest of the loop write itself.
  2. lo = mid + 1a[mid] was too small, so mid cannot be the answer and must leave the range. The + 1 is not optional.
  3. hi = midmid might be the answer, and because hi is exclusive, setting it to mid keeps mid in the range while still shrinking it.
  4. stuck(a, 51)Run under a step cap on purpose. An inclusive hi with lo = mid can reach a state where neither end moves — the loop is alive and making no progress.
Change one thing
  • Change hi = mid to hi = mid - 1 in search and look for the value that is now missed. The bug is silent, which is why the invariant matters more than the shape.
  • Return lo instead of -1 on a miss. That is bisect_left, and it is the version most real problems want.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 4
Answer without scrolling back up.
  1. In the half-open form, what does hi mean?
  2. Why must one branch be lo = mid + 1 rather than lo = mid?
  3. What does lo hold when the loop exits?
  4. Why does lo + (hi - lo) // 2 appear in C implementations?





 Cheat sheet
Write binary search without an off-by-one
Keep a half-open range [lo, hi) and the loop writes itself: while lo < hi, lo = mid + 1 or hi = mid. Both branches strictly shrink the range, which is what guarantees termination — and hi = mid with an inclusive hi is the version that hangs.
INTERVIEW · vizlearn.in/interview/binary-search-without-an-off-by-one.html
More in Interview
InterviewFirst and last position of a targetInterviewBinary search on the answer, not the arrayInterviewClimbing stairs: the DP that is FibonacciInterviewCoin change, and why greedy is wrong
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact