Play the guessing game. I think of a number between 1 and 100; you guess; I answer "higher" or "lower". Nobody sane guesses 1, 2, 3, 4... Everyone guesses 50 — then 75 or 25 — then keeps halving. Seven guesses finish ANY number, guaranteed, because 2⁷ > 100.
You already run binary search in your head. So why does it deserve a full lesson? Because between "I get the idea" and "my code works on the first try" lies the most infamous off-by-one minefield in programming — and because the idea stretches much further than arrays: by the end, you will binary search answers to problems that have no array at all.
The problem, and the naive scan
Task: is 23 in [4, 9, 15, 23, 31, 42, 57]? The natural solution checks left to right — O(n), and for an unsorted pile of numbers, genuinely the best anyone can do (any skipped element could have been the target).
But this array is sorted — and the scan completely ignores that gift. When you looked up "mango" in a dictionary (the BST lesson's opening), did you start at page 1?
The observation sortedness gives us
Look at the middle element, 23... let's make it harder: search for 30. Middle is 23. What do we now know about the entire left half? Every element there is ≤ 23 < 30 — so 30 cannot be among them. One comparison just eliminated half the candidates, proven-safely.
Repeat on the surviving half, and the candidates shrink 7 → 3 → 1 → 0. Halving until one remains is log₂ n steps (lesson 1's ladder): 1 lakh elements → 17 looks; 10 lakh → 20. Doubling the data adds ONE look. That absurd scaling is the entire reason the world keeps data sorted.
The template (learn ONE, exactly)
Now the minefield. Binary search bugs come almost entirely from mixing incompatible template variants — lo < hi from one book with hi = mid from another. The defence: learn ONE consistent template as a unit, and never improvise mid-round. Here is ours, with each choice explained:
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1 # INCLUSIVE range [lo..hi]
while lo <= hi: # <= : a 1-element range still gets checked
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
lo = mid + 1 # mid was checked -> exclude it
else:
hi = mid - 1 # same on the other side
return -1 # range empty: not presentThe three commitments form one consistent set: [lo..hi] is inclusive, so a one-element range means lo == hi and the loop must still run — hence lo <= hi; and mid has been examined, so both updates step PAST it — mid + 1, mid − 1. Change any one commitment and the other two must be re-derived. That's the whole discipline.
Dry run: found, and not found
arr = [4, 9, 15, 23, 31, 42, 57] target 23: lo=0 hi=6 mid=3 arr[3]=23 -> FOUND, return 3 (one look!) target 30: lo=0 hi=6 mid=3 23 < 30 -> lo=4 lo=4 hi=6 mid=5 42 > 30 -> hi=4 lo=4 hi=4 mid=4 31 > 30 -> hi=3 lo=4 hi=3 -> lo > hi, range empty -> return -1 note where it died: lo=4 is exactly where 30 WOULD be inserted - a free by-product (Python calls it bisect_left)
Reproduce the target-30 trace on paper once. The moment lo crosses hi, the inclusive range [4..3] contains nothing — that's what "not present" looks like mechanically.
Why it can't loop forever
A one-sentence proof worth owning: every iteration either returns, or moves lo up / hi down past mid — so the range strictly shrinks every single iteration, and a shrinking integer range must hit empty. Infinite loops in binary search always trace back to an update that can fail to shrink (like lo = mid on a two-element range — try it and watch mid stick). If you ever modify the template, re-check this one property first.
The mid formula and a famous bug
Why lo + (hi − lo) // 2 instead of the obvious (lo + hi) // 2? In Python — no difference; integers never overflow. In Java/C++, lo + hi can exceed the 32-bit limit when both are large and wrap into garbage. This exact bug sat inside Java's own standard-library binary search for nine years before discovery. Same midpoint, immune arithmetic — interviewers ask about it to separate "typed the formula" from "knows why".
First and last occurrence
Real arrays have duplicates: [5, 7, 7, 8, 8, 8, 10]. Plain binary search for 8 returns some 8 — which one is luck. Most real questions want the first or last (counting occurrences, insertion points, ranges).
Pause — how would you adapt the template? What should change when arr[mid] == target?
The upgrade is one idea: finding the target is no longer a reason to stop. Record mid as a candidate, then keep searching the left half — an earlier 8 might exist:
def first_occurrence(arr, target):
lo, hi, ans = 0, len(arr) - 1, -1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
ans = mid # candidate...
hi = mid - 1 # ...but is there an earlier one?
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return ans
print(first_occurrence([5, 7, 7, 8, 8, 8, 10], 8))Result
3
Still O(log n) — the range still halves every step. Mirror it (lo = mid + 1 on a hit) for the last occurrence; count = last − first + 1, two searches. Python ships these as bisect_left / bisect_right — knowing the library AND being able to write it is the winning combination.
Rotated arrays: one side is always clean
The product-company favourite: [15, 18, 2, 3, 6, 12] — sorted, then rotated. Not sorted any more, so binary search is dead... or is it? Look at any midpoint and both halves. What's always true about at least one of them?
A rotated array is two sorted runs with one cliff between them — and any midpoint puts the cliff on ONE side, leaving the other side a perfectly sorted run. A sorted run can answer "is the target inside my range?" with two comparisons. So: identify the clean side, ask it, keep the correct half:
def search_rotated(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
if arr[lo] <= arr[mid]: # LEFT side is the clean run
if arr[lo] <= target < arr[mid]:
hi = mid - 1 # target provably inside it
else:
lo = mid + 1 # provably not -> other half
else: # RIGHT side is the clean run
if arr[mid] < target <= arr[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_rotated([15, 18, 2, 3, 6, 12], 6))Result
4
Still halving, still O(log n) — the guarantee survived because SOME half is always safely discardable. That, not "sorted array", turns out to be binary search's real requirement. Which sets up the biggest upgrade of the lesson.
Binary search on the ANSWER
A problem with no array anywhere: Koko eats banana piles [3, 6, 7, 11] within 8 hours; at speed k she takes ⌈pile/k⌉ hours per pile. Find the minimum sufficient speed.
Where could binary search possibly live here? Ask of each candidate speed: "can Koko finish at speed k?" Speed 1 — too slow. Speed 11 — easily. And crucially, feasibility is monotonic: if k works, everything above k works. Line up the candidate answers and their verdicts:
speed: 1 2 3 4 5 ... 11
feasible? no no no YES YES ... YES
^ the boundaryA row of no's followed by yes's — conceptually a sorted array of booleans, and the answer is the boundary. Halve your way to it:
import math
def min_speed(piles, h):
def feasible(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles) # answer certainly in [1, max pile]
while lo < hi: # boundary-finding template
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid works: it MIGHT be the answer - keep it
else:
lo = mid + 1 # too slow: answer is beyond mid
return lo
print(min_speed([3, 6, 7, 11], 8))Result
4
Verify: speed 4 → 1+2+2+3 = 8 hours ✓; speed 3 → 1+2+3+4 = 10 ✗. Two notes on the code: this is the boundary template (lo < hi, hi = mid — a feasible mid stays a candidate), deliberately different from the find-a-value template; and each "comparison" is now a whole feasibility computation — the halving saves real money here.
The recipe generalises: "minimum (or maximum) X such that ⟨condition⟩" + monotonic condition = binary search on the answer. Ship capacities, aggressive cows, splitting arrays — same recipe, different nouns. It's the pattern that turns binary search from a lookup trick into a problem-solving weapon.
What if...?
What if the array is empty? hi = −1, the lo <= hi check fails immediately, return −1. The template survives its smallest case — always verify this by head.
What if the data is unsorted? No error, no crash — just confidently wrong answers, because the discard step's proof needed sortedness. Binary search fails silently on unsorted data; that's worse than crashing. Check the precondition out loud.
What if it's a linked list? Legal but pointless: reaching the middle costs O(n) walking, which swallows the entire benefit. Binary search needs O(1) access to the middle — arrays, or answer-spaces.
What if duplicates fill the whole array — [8, 8, 8, 8]? Plain search returns some index instantly; first/last occurrence still O(log n). But in rotated-array search, duplicates can make "which side is clean?" undecidable (arr[lo] == arr[mid] == arr[hi]) — the honest fallback shrinks the range by one, degrading to O(n) worst case. A strong thing to say unprompted.
Common mistakes
- Mixing templates —
lo < hiwithhi = mid − 1skips elements;lo <= hiwithhi = midloops forever. - Returning the first FOUND duplicate when the question asks for first/last occurrence.
- Binary searching unsorted data — silent wrong answers.
- In rotated arrays, testing the target before identifying the clean side — the order of questions matters.
- In search-on-answer, choosing bounds that might exclude the answer — lo must be a possibly-infeasible floor, hi a certainly-feasible ceiling; generous bounds cost only log of the extra range.
- Forgetting that each check in search-on-answer costs real time — overall cost is O(log range × cost of one check).
How do I recognise binary search problems?
- Sorted input + "find / position / count occurrences" → the templates, directly.
- "Sorted then rotated" → clean-side reasoning.
- "Minimum X such that..." / "maximise the minimum..." → test the condition for monotonicity; if yes, binary search the answer space.
- An expensive yes/no check you'd otherwise run for every candidate (first bad version, threshold hunting) → the boundary template, minimising calls.
The unifying test — more fundamental than "is it sorted?": can one check safely eliminate half the candidates? If yes, something here wants to be binary searched.
Quick revision
| Variant | Time | Loop shape | Key line |
|---|---|---|---|
| Classic find | O(log n) | lo <= hi | mid ± 1 on both sides |
| First / last occurrence | O(log n) | lo <= hi | record candidate, keep halving |
| Rotated array | O(log n) | lo <= hi | one side is always sorted — ask it |
| On the answer | O(log range × check) | lo < hi | feasible → hi = mid (keep the candidate) |
One thing to remember
Don't think "find the number" — think "eliminate half the possibilities, provably, every step." Anything that supports that elimination — a sorted array, a rotated one, a space of candidate answers — is binary search territory.
Practice Zone — PYQs from real selection rounds
Six MCQs, then three full dry runs: the classic template on present and absent targets, first/last occurrence, and Koko's bananas end to end.
Binary search requires the input to be:
Asked in
Searching 10,00,000 sorted records, binary search needs at most about:
Asked in
Why do careful implementations write mid = lo + (hi - lo) // 2 instead of mid = (lo + hi) // 2?
Asked in
In [5, 7, 7, 8, 8, 8, 10], finding the FIRST occurrence of 8 requires, upon seeing arr[mid] == 8:
Asked in
In the rotated sorted array [15, 18, 2, 3, 6, 12], binary search still works because:
Asked in
"Minimum eating speed to finish all banana piles within h hours" is solved with binary search over speeds because:
Asked in
Hands-on tasks:
Search for 23 in [4, 9, 15, 23, 31, 42, 57]. Write the lo/hi/mid values of every iteration; then repeat for 30 (absent).
Asked in
In [5, 7, 7, 8, 8, 8, 10], return the first and last index of 8 in O(log n) — the count of 8s follows for free.
Asked in
Piles [3, 6, 7, 11], h = 8 hours; eating speed k means each pile takes ceil(pile/k) hours. Find the minimum feasible k via binary search over k.
Asked in
FAQ
Recursive or iterative binary search?
Iterative, by default: O(1) space, no recursion limit, and the invariant is easier to state. The recursive version is fine when asked — volunteer the O(log n) stack cost unprompted, the same habit as with linked list recursion.
Is it worth binary searching small arrays?
Correctness-wise sure; performance-wise at n = 50 a linear scan is comparable and simpler. Binary search earns its keep at scale — or when each check is expensive, as in search-on-answer, where even a small range of candidates hides costly feasibility computations.
How do bisect_left and bisect_right map to this lesson?
bisect_left(arr, x) returns the first index where x could be inserted keeping order — equal to the first occurrence's index when x is present. bisect_right is one past the last occurrence. Count = right − left. They are the boundary variants, productionised.
How do I pick lo and hi for binary-search-on-answer?
A floor that might be infeasible and a ceiling that is certainly feasible: eating speeds → 1 and max(piles); ship capacity → max(weights) (must carry the heaviest single package) and sum(weights) (one trip carries all). Generous is fine — correctness beats tightness, and slack costs only log of the extra range.
Halving mastered, in arrays and beyond. Next, two more ways to kill nested loops — with pointers and windows — Lesson 3: Two Pointers & Sliding Window →