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.

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."

Overview

Binary search keeps a range of candidates and removes half after each comparison. A half-open interval [lo, hi) makes the invariant and termination explicit; the same convention supports insertion-point searches and duplicate boundaries.

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.

                

                

                    
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.

                

                

                    
Sources and next steps

                    
                

            


        

    



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
Write binary search that terminates correctly every time. Trace the loop invariant, see where off-by-one errors hide, and fix them before they bite.
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