Binary Search

1The mental model (what this really is)#

Drop "searching a sorted array" for a second. That is the first example people learn, and it traps them into thinking binary search only works on arrays.

The real idea.

• You have a space of possible answers.
• You can ask one yes/no question about any candidate, and that question splits the space cleanly: one side is "too small / no," the other is "good enough / yes."
• So you never check every candidate. Check the middle, throw away the wrong half, repeat.
• Each step halves the work, so 1 billion candidates fall to 1 in about 30 steps (2^30 is just over a billion).

That property has a name: monotonicity.

• The yes/no answer flips exactly once as you move across the space.
• Sorted array lookup is just the simplest case, where the question is "is this element at least my target?"
• Once you see it as "find the boundary in a monotonic predicate," you stop needing an array at all.
• The thing you search over can be an index, a number, a capacity, a speed, or a time.

2How to recognize it (the signals in a problem)#

Train your eyes for these. Any one should make you ask "is this binary search?"

• Sorted input (or sortable) and you want a specific value or a boundary.
• "Minimum X such that it works" or "maximum X such that it still works." The words minimum, maximum, smallest, largest, least next to a feasibility check are the loudest signal there is.
• Big range, cheap check. Brute force would try every value in a huge range (10^9 or more), but checking one value is cheap (say O(n)). That gap screams "binary search the answer."
• Sorted but rotated, or some near-sorted structure. Interviewers add rotation specifically to see if you get the mechanism, not just the memorized form.
• The constraints demand O(log n). If N is 10^5 and the expected complexity is better than O(N), log N is usually the target.

Run the numbers on that third signal so it sticks.

• N around 10^5, value range around 10^9.
• An O(N) scan per candidate across the whole range is 10^14 operations. Times out.
• O(N log(range)) is about 10^5 times 30, roughly 3 million. Finishes instantly.

3The template (how it works, with pseudocode)#

Here is the version I trust most and why. There are three common styles. Pick one and use it for everything, because flip-flopping under stress is how people create off-by-one bugs at minute 15 and never recover.

My default: half-open boundary search.

• You are not looking for an exact match. You are finding the first index (or value) where a condition becomes true.
• This form answers almost every binary search question with no special-casing.

# find the smallest x in [lo, hi) where predicate(x) is True
# predicate must be monotonic: False...False, True...True

def binary_search(lo, hi):
    while lo < hi:
        mid = lo + (hi - lo) // 2    # avoids overflow in some languages
        if predicate(mid):
            hi = mid                 # mid might be the answer, keep it in range
        else:
            lo = mid + 1             # mid is not it, discard it
    return lo                        # lo == hi == first True (or hi if none)

Three things make this bulletproof.

1. The loop condition is lo < hi, so the window shrinks every iteration and always terminates. On the True branch hi strictly drops (because mid < hi whenever lo < hi); on the False branch lo strictly rises.
2. When the predicate is true at mid, keep mid as a candidate with hi = mid, not hi = mid - 1. That one choice kills the most common off-by-one bug.
3. The return is lo, the first index where the predicate holds. If nothing satisfies it you get hi, which means "no answer in range." So always pass hi as one past the last valid candidate, not the last candidate itself.

Need the last True instead of the first?

• Flip the predicate, or search for the first False and step back.
• Do not write a second template. Reframe the question so this one fits.
• I mean that literally: in five years of interview loops I have never needed a second shape.

For the classic "find exact target in a sorted array":

• Predicate is arr[mid] >= target, then check lo < len(arr) and arr[lo] == target at the end.
• The lo < len(arr) guard matters: when the target is larger than everything, lo lands on len(arr) and indexing it crashes.

4A worked example (walk through one problem step by step)#

Let me do a "minimize the max" problem, because that is the kind people miss.

Problem (Koko eating bananas, in spirit): There are piles of bananas, piles = [3, 6, 7, 11]. Koko has h = 8 hours. Each hour she picks one pile and eats up to k bananas from it; if the pile is smaller than k, she finishes it and the hour is done. Find the smallest eating speed k so she finishes all piles within h hours.

First, recognize it.

• "Smallest k such that she finishes in time." Minimum X such that something works.
• Binary search on the answer.

The range.

• Slowest useful speed is 1 banana per hour.
• Fastest worth considering is the biggest pile, 11, because eating faster than the biggest pile does not help: you still spend exactly one hour on it.
• So k lives in [1, 11].

The predicate.

• canFinish(k): can Koko eat everything in h hours at speed k?
• For each pile the hours needed are ceil(pile / k). Sum them. Return True if the total is at most h.
• This check is O(number of piles), so O(4) here and O(n) in general.

Is it monotonic? Yes, and I say this out loud in the room.

• A faster speed never takes more hours, since ceil(pile / k) is non-increasing in k.
• So as k increases, canFinish goes False, False, ..., True, True. One flip.
• I want the first True.

Run it on the data. Range is lo = 1, hi = 12 (half-open, so hi is one past 11).

• mid = 1 + (12-1)//2 = 6. Hours at 6: ceil(3/6)=1, ceil(6/6)=1, ceil(7/6)=2, ceil(11/6)=2. Total = 6, which is <= 8. True, keep it: hi = 6.
• Window [1, 6). mid = 1 + (6-1)//2 = 3. Hours at 3: 1, 2, 3, 4. Total = 10, which is > 8. False, discard: lo = 4.
• Window [4, 6). mid = 4 + (6-4)//2 = 5. Hours at 5: 1, 2, 2, 3. Total = 8, which is <= 8. True, keep: hi = 5.
• Window [4, 5). mid = 4. Hours at 4: 1, 2, 2, 3. Total = 8. True, keep: hi = 4.
• Now lo = 4, hi = 4. Loop ends. Answer is 4.

What just happened.

• The smallest speed is 4 bananas per hour.
• I never looped over all of 1 to 11. I made four predicate calls.
• If the range were 1 to a billion it would still be about 30 calls, because log2(10^9) is roughly 30. That is the whole point.

The move to remember.

• The template did the bookkeeping. All I invented was the range and the predicate.
• In almost every hard binary search, the hard part is naming the predicate, not writing the loop.
• Stuck in an interview? Say out loud "let me define the feasibility check first," and the structure usually falls out.

Here is the full solution, so you see how little code wraps the template:

def minEatingSpeed(piles, h):
    def canFinish(k):
        hours = 0
        for p in piles:
            hours += (p + k - 1) // k   # ceil(p / k) without floats
        return hours <= h

    lo, hi = 1, max(piles) + 1          # half-open: hi is one past the max pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if canFinish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

5Variations and gotchas#

Lower bound vs upper bound.

• "First element >= target" (lower bound) and "first element > target" (upper bound) differ only in >= vs > inside the predicate.
• Keep both in your head: many problems want occurrence counts via upper - lower.
• That subtraction is the clean O(log n) way to answer "how many times does 5 appear?"

Rotated sorted array.

• Sorted but rotated at an unknown pivot, like [4,5,6,7,0,1,2]. You cannot compare arr[mid] to the target directly.
• At each step one half is guaranteed sorted. Find which (compare arr[lo] to arr[mid]: if arr[lo] <= arr[mid] the left half is sorted, else the right), check if the target falls in that sorted half's range, and move accordingly.
• Still binary search. You just enrich the decision.
• Duplicates like [1,1,1,0,1] break the comparison and force an O(n) worst case, so call that edge out if repeats are allowed.

Binary search on a real-number / float answer.

• When the answer is continuous (minimum time, minimum capacity as a decimal), replace the integer loop with a fixed number of iterations (say 100) or loop until hi - lo < epsilon, with epsilon around 1e-6 or whatever the problem wants.
• Do not use lo < hi on floats: rounding means it may never terminate.

Search on 2D matrices.

• A matrix sorted row-wise and column-wise, where each row continues from the previous, can be treated as a flattened sorted array (index i maps to row = i // cols, col = i % cols), giving O(log(rows * cols)).
• If rows do not continue from each other, a staircase walk from the top-right corner is often cleaner and runs in O(rows + cols).

Peak / unsorted but structured.

• Finding a peak element works even without sorting: you can always move toward the higher neighbor, and a peak must exist in that direction.
• The monotonic property is local, not global.
• This surprises people, and it is a favorite because it proves you understand why binary search works rather than when to type it.

6Complexity#

Time.

• O(log N) where N is the size of the search space, times the cost of one predicate check.
• Plain array lookup: predicate is O(1), so O(log n).
• Binary search on the answer with an O(n) feasibility check: O(n log(range)).
• That log(range) is often tiny: 30 iterations for 10^9, about 60 for 10^18. These solutions feel instant even when the brute force would run for hours.

Space.

• O(1) for the iterative form.
• The recursive form costs O(log N) stack frames, which is why I prefer iterative in interviews: one less thing to explain, and no stack-overflow story on adversarial inputs.

7Mistakes that cost people the round#

• Off-by-one in the boundary. Writing hi = mid - 1 when mid could be the answer, or using lo <= hi with a half-open window. Pick the one template above and stop improvising. This single discipline removes most binary search bugs.
• Infinite loops. Setting lo = mid (instead of mid + 1) on the False branch, where mid keeps landing on lo (which happens whenever hi - lo == 1), loops forever. Always advance past mid on the side you discard.
• Not proving monotonicity out loud. Interviewers want to hear "this predicate is monotonic because a faster speed never needs more hours." If you cannot say it, binary search may not even be valid. I have failed candidates who had the right code but could not justify why the predicate flips exactly once.
• Choosing the wrong search range. Too narrow and you miss the answer; too wide and you waste checks or hit edge bugs. For "minimize the max," the low end is usually the largest single element, not 1, because no split can ever be smaller than the biggest item. Decide the extreme feasible values before you type lo and hi.
• Integer overflow on (lo + hi) / 2. In fixed-width-int languages like Java or C++, lo + hi can overflow a 32-bit int near 2^31; use lo + (hi - lo) / 2. Mention it even in Python, where ints are arbitrary precision: it signals you have shipped real code in a language where it bites.
• Confusing "find the value" with "find the boundary." For duplicates or "first/last position," a plain match is wrong: you might land on any copy. You want the boundary form that pins down the leftmost or rightmost.

8Your practice path (named problems by difficulty)#

Do them in this order. Each step adds exactly one new idea, so do not skip ahead; the later groups assume the muscle from the earlier ones.

Warm up (classic form):

• Binary Search
• Search Insert Position
• First Bad Version
• Sqrt(x)

Build the boundary muscle:

• Find First and Last Position of Element in Sorted Array
• Find Peak Element
• Search a 2D Matrix

Rotation and twists:

• Search in Rotated Sorted Array
• Find Minimum in Rotated Sorted Array
• Single Element in a Sorted Array

Binary search on the answer (the interview differentiator):

• Koko Eating Bananas
• Capacity To Ship Packages Within D Days
• Split Array Largest Sum
• Minimum Number of Days to Make m Bouquets

Boss level:

• Median of Two Sorted Arrays
• Find K-th Smallest Pair Distance

Solve the "binary search on the answer" group cold, naming the range and predicate without hints, and you are ahead of most candidates, because that is where recognition is hardest and the payoff is biggest. The boss-level two are genuinely hard; treat them as stretch goals, not blockers.

9Where this shows up (which companies and rounds lean on it)#

Binary search is a staple of the phone screen and the first onsite coding round almost everywhere.

• Amazon leans hard on "binary search on the answer" capacity and scheduling framings that mirror their real logistics: ship packages in D days, allocate throughput, meet a deadline.
• Google and Meta favor rotated-array and boundary variants to test whether you understand the mechanism, and they push on "why does this terminate?" or "what if there are duplicates?"
• Resource-allocation and systems-heavy companies reach for the "minimize the max" style constantly.
• Expect at least one binary-search-flavored question in any multi-round loop. It is cheap to pose and reveals a lot in 20 minutes.

Want to see which of your target companies lean on this pattern and how they phrase it? Check the company guides to map this pattern to the rounds you will actually face.