Binary Search —
Simple to describe, easy to get wrong live.
Everyone knows the idea — halve the search range each step. What actually separates candidates is the boundary conditions: off-by-one errors in the pointer updates are the single most common live-coding mistake on this problem. This page focuses on those edge cases and the variants interviewers layer on top.
Why do boundary conditions trip people up?
Every version of binary search has small decisions — left <= right vs left < right, mid + 1 vs mid — that look interchangeable but aren't. Getting even one wrong causes an infinite loop or a missed element, and it's exactly the kind of subtle bug that's hard to spot by just reading the code back.
Why visualization helps
Watching left, mid, and right converge correctly on a working example — and watching them fail to converge on a broken one — makes the difference between the correct and incorrect boundary logic concrete instead of something you have to trust by memorizing a template.
Three shapes this question commonly takes
Standard — find the exact index
Return the index of the target, or -1 if not present. The baseline version — get this exactly right before attempting any variant.
First/last occurrence of a duplicate
When the target appears multiple times, don't stop at the first match — keep narrowing in the direction that finds the boundary you need.
Rotated sorted array
The array is sorted but rotated at an unknown pivot — one half is always properly sorted, and figuring out which half is the key insight.
Boundary conditions interviewers probe
Why left <= right, and not left < right?
<= allows the loop to check the case where left == right — a single remaining candidate. Using < instead would exit the loop before checking that last element, silently missing the target if it happens to be at that final remaining position.
Why mid + 1 and mid - 1, not just mid, when updating the pointers?
Once you've confirmed arr[mid] isn't the target, mid itself is fully eliminated — including it again in the next range (by setting left = mid instead of mid + 1) can cause the range to stop shrinking, producing an infinite loop.
How do you compute mid without risking integer overflow?
(left + right) // 2 can theoretically overflow in languages with fixed-size integers if left and right are both very large — the safer form is left + (right - left) // 2. Python's integers don't overflow, but mentioning this shows awareness that's expected in some interview contexts (especially C++/Java shops).
How do you find the FIRST occurrence when duplicates exist?
When arr[mid] == target, don't return immediately — record it as a candidate and keep searching the left half (right = mid - 1) to see if an earlier occurrence exists. The last recorded candidate when the loop ends is the first occurrence.
How do you binary search a rotated sorted array?
At each step, one half (left-to-mid or mid-to-right) is guaranteed to be properly sorted — compare arr[left] to arr[mid] to figure out which half that is, then check if the target falls within that sorted half's range to decide which side to continue searching.
What if the array is empty, or the target isn't present at all?
An empty array means left starts greater than right, so the loop never executes and the function correctly returns "not found" immediately. A target genuinely absent from a non-empty array causes left and right to cross without ever matching — also handled correctly if the loop condition is right.
The standard version, with the boundary logic annotated
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right: # <= checks the last remaining candidate
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1 # mid is eliminated — move past it
else:
right = mid - 1 # mid is eliminated — move before it
return -1Quick Reference
Watch left, mid, and right converge — or fail to
Paste your binary search into LearnBug and check the boundary logic live.