Binary Search: The Complete Interview Guide (with Templates)

Almost nobody fails binary search because they do not understand halving. They fail on the boundary — one wrong character in whether hi becomes mid or mid - 1, an off-by-one that passes the first example and dies on a two-element array with the interviewer watching. The idea takes thirty seconds to explain. The discipline takes deliberate practice, and this post is about the discipline.

The plan: one template, its invariant actually proved rather than asserted, in both Python and Java. Then everything else — lower bound, upper bound, first occurrence, counting duplicates, rotated arrays, 2D matrices — as a change of predicate rather than a change of loop.

The one template

Every variant below is the same question in disguise: given a predicate that is false for a while and then true forever, find the first index where it flips. That monotone shape — F F F F T T T — is the only thing binary search needs. Sortedness is just the most common way to get it.

def first_true(lo, hi, pred):
    """Smallest x in [lo, hi] with pred(x) True.

    Requires pred to be monotone over the range: once True, always True.
    `hi` must be known-True, or be a sentinel meaning "no answer exists".
    """
    while lo < hi:
        mid = lo + (hi - lo) // 2   # floor, so lo <= mid < hi
        if pred(mid):
            hi = mid                # mid is still a candidate — keep it
        else:
            lo = mid + 1            # mid failed — it can never be the answer
    return lo

import java.util.function.IntPredicate;

/** Smallest x in [lo, hi] with pred true; pred must be monotone over the range. */
static int firstTrue(int lo, int hi, IntPredicate pred) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;   // never (lo + hi) / 2 — see below
        if (pred.test(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

The invariant, stated and proved

Call the answer A — the smallest index in the range where pred is true, or the initial hi if the predicate is never true.

Invariant: at the top of every iteration, A lies in the closed interval [lo, hi].

It holds at the start. We chose lo and hi to bracket the whole search space, so trivially A is inside it.

Each branch preserves it. If pred(mid) is true, then by monotonicity nothing above mid can be the first true, so A <= mid and [lo, mid] still contains it — that is why the true branch keeps mid. If pred(mid) is false, then by monotonicity nothing at or below mid can be true either, so A > mid and [mid + 1, hi] still contains it.

It terminates. Because the midpoint floors and lo < hi, we always get lo <= mid < hi. So hi = mid strictly decreases hi and lo = mid + 1 strictly increases lo. The interval shrinks every iteration; it cannot stall.

So the exit is correct. The loop ends when lo == hi, and the invariant says A is in [lo, hi] — an interval of one element. That element is lo.

Being able to say that out loud matters. "I use this template" is a weaker answer than "I use this template and here is why its exit condition is forced."

Last-true is the same search

You do not need a second template for "the last index where the predicate is true." A monotone T T T F F F is just F F F T T T for the negated predicate, so last_true(pred) = first_true(not pred) − 1, and a result of lo - 1 means nothing satisfied it. Deriving it that way takes five seconds and is far safer than recalling a second loop with lo = mid in it — which, as the failure modes below show, is where the infinite loops live.

Why lo + (hi - lo) / 2 matters, and where it does not

(lo + hi) / 2 is correct mathematics and a latent bug in any fixed-width integer language. In Java, lo and hi are 32-bit ints; if both are large their sum exceeds Integer.MAX_VALUE, wraps negative, and the division yields a negative index. Joshua Bloch published a widely-cited 2006 note about finding exactly this overflow inside the JDK's own Arrays.binarySearch, where it had gone unnoticed for years. The JDK's fix was the unsigned shift (lo + hi) >>> 1, equally safe; lo + (hi - lo) / 2 is the version that reads the same in every language.

In Python the overflow cannot happen — integers are arbitrary precision. I write the subtraction form anyway, because you will write this in Java or C++ eventually and a habit that is safe everywhere beats one you have to remember to switch. Be honest about the scale if asked: you need lo + hi above roughly 2.1 billion, so an interview-sized array will never expose it. You write it because it costs nothing and because the person across the table recognises it.

Lower bound and upper bound

These two are the entire sorted-array toolkit, and both are first_true with a different comparison.

• Lower bound — first index with arr[i] >= target. This is Python's bisect_left.
• Upper bound — first index with arr[i] > target. This is Python's bisect_right.

from bisect import bisect_left, bisect_right

def lower_bound(arr, target):
    return first_true(0, len(arr), lambda i: arr[i] >= target)

def upper_bound(arr, target):
    return first_true(0, len(arr), lambda i: arr[i] > target)

first = lower_bound(arr, target)                 # == bisect_left(arr, target)
present = first < len(arr) and arr[first] == target
count = upper_bound(arr, target) - first         # == bisect_right - bisect_left

Note the range: hi starts at len(arr), not len(arr) - 1. That extra slot is the sentinel — "every element is smaller than the target" returns len(arr), which is also exactly the insertion point. Search Insert Position is lower_bound with nothing added.

Three classic questions then fall out with no new code: first occurrence is lower_bound plus an equality check, last occurrence is upper_bound - 1 with the same check, and how many times does the target appear is upper_bound - lower_bound — no scan, no counting loop.

int lo = firstTrue(0, a.length, i -> a[i] >= target);   // lower bound
int hi = firstTrue(0, a.length, i -> a[i] > target);    // upper bound
boolean present = lo < a.length && a[lo] == target;
int count = hi - lo;

The Java library trap

Arrays.binarySearch looks like it does this for you. It does not, and the javadoc is unusually blunt about why: if the array contains multiple elements equal to the search key, there is no guarantee which one will be found. It may hand you the middle of a run of duplicates. Collections.binarySearch carries the same caveat.

Know its return convention too, because interviewers ask: on a miss it returns -(insertion point) - 1, so you recover the insertion point as -(result) - 1. The minus-one exists so a miss is always negative, including a miss at index 0.

The takeaway: the JDK ships no lower-bound or upper-bound for arrays. TreeMap and TreeSet give you ceiling, floor, higher and lower with those semantics; for an int[], write the four lines above.

Rotated arrays

Search in Rotated Sorted Array is the most-asked variant, and the reasoning everyone repeats — "one half is always sorted" — is usually asserted rather than argued. Here is the argument.

Take a sorted array of distinct values rotated at some pivot. There is at most one place in it where a descent happens — the seam where the largest value is followed by the smallest, and none at all if the rotation happened to be zero. Now cut the array at mid. That produces two pieces, and a single seam can live in at most one of them. Therefore at least one piece contains no descent, which is to say it is sorted. That is not a heuristic; it is a counting argument, and it is what makes the next step legal.

Which piece? Compare the endpoint to the midpoint. If arr[lo] <= arr[mid], no descent occurred between them, so the left piece is the sorted one; otherwise the seam is on the left and the right piece is sorted. Once you know a piece is sorted, you can test membership against its two endpoints in O(1) and discard 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 piece [lo, mid] is sorted
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                      # right piece [mid, hi] is sorted
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

That is the expected answer and you should be able to write it — but notice it is a second loop shape, the classic exact-match lo <= hi form. If you would rather not carry two, you can stay inside the one template by finding the rotation offset first and searching through it:

def find_min_rotated(arr):
    last = arr[-1]
    return first_true(0, len(arr) - 1, lambda i: arr[i] <= last)   # index of the minimum

def search_rotated_via_pivot(arr, target):
    n, p = len(arr), find_min_rotated(arr)
    # Virtual index j maps to real index (j + p) % n — and the virtual array IS sorted.
    j = first_true(0, n, lambda j: arr[(j + p) % n] >= target)
    return (j + p) % n if j < n and arr[(j + p) % n] == target else -1

find_min_rotated is the cleanest illustration of the whole idea: the array is not sorted, yet arr[i] <= arr[-1] is perfectly monotone over it — everything before the seam exceeds the last element, everything from the seam onward does not. F F F F T T T. Binary search never required a sorted array; it required a monotone predicate.

The duplicates caveat, which is the follow-up question: if values can repeat, arr[lo] == arr[mid] == arr[hi] tells you nothing about which side the seam is on. You cannot discard half; you shrink by one and the worst case degrades to O(n). Say that unprompted — knowing where a technique stops working is a stronger signal than the technique itself.

Search a 2D matrix

When a matrix has each row sorted and the first element of every row greater than the last element of the previous one, the row-major reading of it is one sorted array of length rows × cols. So do not write a 2D search — write a 1D search and translate the index.

def search_matrix(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    def value_at(k):
        return matrix[k // cols][k % cols]
    k = first_true(0, rows * cols, lambda k: value_at(k) >= target)
    return k < rows * cols and value_at(k) == target

The bug that bites people here is dividing by the wrong dimension. You divide by cols, the length of a row — k // cols is "how many complete rows have I passed", k % cols is the offset into the current one. On a square matrix the wrong version passes every test you write, which is exactly why it survives to the interview.

One caveat, because these two problems get conflated: a matrix whose rows and columns are individually sorted but whose rows do not chain end-to-start is not a flattened sorted array, and this technique is wrong on it. That one is the staircase walk from the top-right corner, O(rows + cols). It is not binary search, and calling it binary search is a real mistake rather than a naming quibble.

Recognition cues

The other life of this pattern

Everything above searches an array. There is a whole second life to binary search where there is no array at all: you bisect the answer itself over a numeric range, using a feasible(x) check that is false below a threshold and true from it onward. Minimum eating speed, minimum ship capacity, split-array largest sum — none contain a sorted array, and all are this same first_true with pred swapped for a feasibility function. That family is big enough to deserve its own post and is getting one; the mechanism is the template you just learned, so you have already done the hard part.

Failure modes

The boundary off-by-one. The one that actually costs offers. hi = mid and hi = mid - 1 are both correct — in different templates — and mixing them silently drops the answer when the answer is mid. The fix is not care, it is commitment: one template, its invariant provable, and no improvising while someone watches you type.

The infinite loop from lo = mid. Any branch that writes lo = mid with a floor midpoint hangs. Concretely: lo = 0, hi = 1 gives mid = 0, and lo = mid leaves both unchanged — forever. The rule is mechanical: a branch that writes lo = mid requires a ceiling midpoint, lo + (hi - lo + 1) // 2. The template here never writes lo = mid, which is why its floor midpoint is safe, and why deriving last-true from first-true beats writing a second loop.

Trusting Arrays.binarySearch on duplicates. It returns an index, not the first. That code returns the right occurrence on some inputs and the wrong one on others — the worst kind of bug to meet in an interview.

Returning the sentinel unchecked. first_true returns hi when nothing satisfies the predicate, so its return value is a candidate, not a result. Either pick a hi you have proved feasible, or validate before using it: k < len(arr) and arr[k] == target. Skipping that is how "not found" becomes an IndexError or, worse, a plausible wrong answer.

Evaluating the predicate out of range. Easy to miss when the predicate touches arr[i + 1] or arr[i - 1], as it does in peak-finding. Check every index your predicate reads against every mid the loop can produce.

Problems worth drilling

Six, each failing for a different reason:

• Search Insert Position — whether your template returns the insertion point for free. Special-case code here means the template is wrong.
• Find First and Last Position of Element in Sorted Array — lower and upper bound as a pair, plus the empty-result case candidates forget to guard.
• Find Minimum in Rotated Sorted Array — whether you can state a monotone predicate over an array that is not sorted. The conceptual centre of the pattern.
• Search in Rotated Sorted Array — whether you argue the one-sorted-half claim rather than assert it, and volunteer the duplicates degradation.
• Search a 2D Matrix — index arithmetic under pressure, and whether you notice which dimension you divide by.
• Find Peak Element — that binary search needs no sortedness at all: one neighbour comparison tells you which half must still contain a peak.

Complexity throughout: O(log n) comparisons. Worth a caveat if the interviewer pushes on real-world performance — that bound counts comparisons, not memory behaviour, and each probe jumps somewhere unpredictable, so on small inputs a linear scan can win on cache locality and branch prediction alone.

Pick one template, prove it once, then drill until the boundary is muscle memory rather than a decision. Build a schedule around it with the free study-plan generator, or work the variants live with feedback in the DSA course.

Binary search is one of seventeen shapes worth recognising on sight — the complete DSA patterns guide has the recognition table and shows how this one composes with the rest.

More interview patterns: Two Pointers · Sliding Window · Dynamic Programming · Graph Algorithms

One breakdown like this per email, whenever a new one publishes — subscribe here.

Amit Singh teaches the DSA Masterclass at AlgoEngineer. He is a Senior SDE at Amazon and a Claude Certified Architect.