Pass the coding test
Binary Search Variants: 7 Templates, Java + Python
Riya has solved 200 problems. Asked to write binary search on paper, she does it in forty seconds. Then: "your array has four equal elements - which index does that return?" She does not know. "Now return the first one." She rewrites it three times, and the third one loops forever .
16 min readFree, no email neededUpdated 11 September 2026
What binary search actually needs
Riya has solved 200 problems. Asked to write binary search on paper, she does it in forty seconds. Then: "your array has four equal elements - which index does that return?" She does not know. "Now return the first one." She rewrites it three times, and the third one loops forever.
Binary search does not need a sorted array. It needs a yes-or-no question whose answer flips from no to yes exactly once as you move right. A sorted array is just the most common way to get one.
Every variant in this guide is the same algorithm asking a different question at that line. "Is nums[mid] the target?" "Is nums[mid] at least the target?" "Is this speed fast enough?" Change the question, keep the machinery.
If you can write the yes-or-no test, and it never flips back from Y to N, you can binary search it. Nothing else is required.
The exact-match template
The invariant, in one sentence: at the top of every loop, if the target is in the array at all, it is inside nums[lo .. hi]. Every branch must keep that promise true. That is the whole algorithm; the rest is arithmetic.
The off-by-one page
Almost every broken binary search is one of these three decisions made without thinking. Decide them on purpose and the bugs stop.
lo <= hi or lo < hi?lo <= hi when you return the answer on sight and hi is a real index still to be tested; it ends with lo > hi, meaning not there. lo < hi when hunting a boundary; it ends with lo == hi, and that surviving index is the answer, so never throw it away.mid = lo + (hi - lo) // 2?Same number as (lo + hi) // 2 in Python. In Java lo + hi can pass 2147483647, wrap negative, and nums[negative] throws. It also rounds down: when lo < hi, mid can equal lo but never hi. That fact decides question 3.hi = mid - 1 or hi = mid?Could mid itself still be the answer? Ruled out, drop it: hi = mid - 1. Still a candidate (first element at least target, a peak, a workable speed): hi = mid. But hi = mid is safe only inside a lo < hi loop; inside lo <= hi the range stops shrinking when lo == hi and it spins forever. And lo = mid is never safe.lo <= hihi = mid - 1lo <= hihi = mid - 1lo < hihi = midlo <= hihi = mid - 1lo < hihi = midlo < hihi = midFirst occurrence
Duplicates are allowed, and you want the smallest index holding the target, or -1. Plain binary search returns whichever copy it happens to land on, which is why the follow-up question exists.
The change: a hit is no longer the end. Save it, then carry on searching the left half in case an earlier copy exists.
Last occurrence, and counting
Same problem mirrored: the largest index holding the target. Exactly one line changes from the previous page, and it is the line that says which way to keep looking.
Free follow-up: "how many times does the target appear?" is last - first + 1, or 0 when first is -1. Here 4 - 1 + 1 = 4, in O(log n) instead of a scan.
Lower bound and upper bound
Lower bound is the first index whose value is at least the target: where the target would be inserted. Upper bound is the first index whose value is strictly greater. Neither cares whether the target exists.
The change: hi starts at n, not n - 1, because the answer can be n itself (everything is smaller than the target). There is no equality branch, and the loop is lo < hi, so mid must be kept when it is still a candidate.
Search in a rotated sorted array
A sorted array was cut once and the pieces swapped: [4, 5, 6, 7, 0, 1, 2]. Comparing the target with nums[mid] alone tells you nothing now.
The insight: cut anywhere and at least one half is fully sorted. Find which, check whether the target lies inside its range, and throw the other half away. The <= matters: with two elements left, lo equals mid.
Find a peak element
A peak is bigger than both its neighbours; anything off either end counts as minus infinity, and no two neighbours are equal. Return the index of any peak, in O(log n). There is no sorted array here at all.
The insight: compare nums[mid] with nums[mid + 1]. Rising? Then the values to the right must either keep rising into the edge or turn down somewhere, and either way a peak exists to the right, so lo = mid + 1. Falling? Then mid itself may be the peak, so hi = mid. Never discard a candidate.
Why mid + 1 is always a valid index: the loop only runs while lo < hi, and mid rounds down, so mid < hi and mid + 1 is at most hi.
Binary search on the answer
This is the one that separates people. There is no sorted array in the input. You invent the array: it is the range of every answer you could possibly give, and you binary search that.
How to spot the shape. Three questions. What is the smallest and largest the answer could be? Given a candidate answer, can I check it in one simple pass? And is that check monotonic: if a value works, does every bigger value also work? Three yes answers means binary search the range.
Same skeleton for minimum capacity to ship packages in D days: the range is from the heaviest single package to the sum of all of them, and feasible(cap) counts how many days that capacity needs.
Koko eating bananas
Koko has piles of bananas and h hours. She picks one speed s and keeps it. Each hour she eats from a single pile; if it has less than s left, she finishes it and waits. Find the smallest s that clears every pile within h hours.
Range: 1 to the largest pile. Check: hours at speed s is the sum of ceil(pile / s). Monotonic: faster never takes more hours. So search the range.
The five mistakes
Each of these either spins forever or quietly returns the wrong index. Every example below was run.
lo = mid instead of lo = mid + 1Spins forever. On [1, 3, 5, 7] looking for 7 it reaches lo = 2, hi = 3, mid = 2, sees 5 < 7, sets lo = 2 again, and repeats that state until the judge kills it. Because mid rounds down, lo = mid can leave the range unchanged. Only lo = mid + 1 is ever safe.while lo <= hi loopSpins forever. When lo == hi you get mid == lo == hi, and hi = mid changes nothing. Pair them properly: lo <= hi goes with hi = mid - 1, and lo < hi goes with hi = mid.nums[lo] == target before returning.hi = len(nums) - 1 for lower boundMisses the answer at the end. The correct reply for "where does 99 go in [10, 20, 30]" is 3, one past the last index. Starting hi at n - 1 caps the answer at 2. Bounds are the one variant where hi starts at n.nums[lo] < nums[mid] in the rotated searchMisses the answer on small ranges. When two elements are left, mid equals lo, so the strict < says "left half not sorted" and the wrong branch runs. On [1, 0] searching for 0 it returns -1 instead of 1. Write nums[lo] <= nums[mid].Want this on your phone?
Everything above, as a PDF built to read on a phone the morning of the interview. It costs nothing — we ask for an email so we can send it, and that is all.