Binary Search Patterns: Classic, Rotated Arrays and Binary Search on Answer

Binary search is the algorithm everyone knows and almost everyone gets subtly wrong under pressure. The idea is trivial; the details (< or <=, mid or mid + 1, return lo or lo - 1) are where interview solutions hang or return the wrong index. Then there is the variant that catches people out completely: problems with no sorted array in sight, such as "minimum eating speed" or "place cows to maximise the minimum distance", which are binary search on the answer itself.

This guide fixes both. It gives you one mental model and two templates, applies them to classic searches and rotated arrays, and then works through the three canonical answer-space problems (Koko Eating Bananas, Aggressive Cows and Book Allocation) with dry runs.

The Core Idea: Binary Search Finds the Boundary of a Monotonic Predicate

Forget "find x in a sorted array" for a moment. Binary search works on any index range where some yes/no question pred(i) is monotonic: false for a prefix, then true for the rest (F F F T T T). The algorithm finds the boundary, the first index where the answer turns true, in O(log n) evaluations.

Once you phrase the problem as a predicate and say whether you want the first or last true, the code is mechanical.

Two Binary Search Templates That Avoid Off-by-One Errors

Template A: first true (minimise)

def first_true(lo, hi, pred):
    """Smallest x in [lo, hi] with pred(x) True. Assumes pred(hi) is True."""
    while lo < hi:
        mid = (lo + hi) // 2          # rounds DOWN, so mid < hi
        if pred(mid):
            hi = mid                  # mid might be the answer; keep it
        else:
            lo = mid + 1              # mid is not; discard it
    return lo

Template B: last true (maximise)

def last_true(lo, hi, pred):
    """Largest x in [lo, hi] with pred(x) True. Assumes pred(lo) is True."""
    while lo < hi:
        mid = (lo + hi + 1) // 2      # rounds UP, so mid > lo
        if pred(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

// first true in [lo, hi]
template <class Pred>
long long firstTrue(long long lo, long long hi, Pred pred) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (pred(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

// last true in [lo, hi]
template <class Pred>
long long lastTrue(long long lo, long long hi, Pred pred) {
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (pred(mid)) lo = mid; else hi = mid - 1;
    }
    return lo;
}

Why the rounding matters

With two elements left, say lo = 4, hi = 5: in Template B, rounding down would give mid = 4; if pred(4) is true, lo = mid = 4 and nothing changes, an infinite loop. Rounding up gives mid = 5, so the range always shrinks. The rule: whichever side is assigned mid, round mid away from that side.

What if no answer exists? Widen the range by one so the "impossible" value acts as a sentinel. For example, search [0, n] for the first index with a[i] >= x, where n means "none"; this is exactly how lower_bound behaves.

The classic exact-match search

For "return the index of target or -1", the familiar closed-interval loop is fine and worth knowing as a third form:

public int search(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;       // never (lo + hi) / 2 with ints
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

The lo + (hi - lo) / 2 form matters: (lo + hi) / 2 overflows when both exceed about 1.07 billion. This bug sat in the JDK's Arrays.binarySearch for years until it was fixed in 2006, and interviewers still ask about it.

lower_bound, upper_bound and bisect: Use the Library When You Can

Java's Arrays.binarySearch returns -(insertionPoint) - 1 when the key is missing, and with duplicates it makes no guarantee about which matching index it returns. So for "first and last position of target" (LeetCode 34), write lower and upper bound yourself:

from bisect import bisect_left, bisect_right

def search_range(nums, target):
    lo = bisect_left(nums, target)
    if lo == len(nums) or nums[lo] != target:
        return [-1, -1]
    return [lo, bisect_right(nums, target) - 1]

Rotated Sorted Arrays: Search and Find Minimum

A sorted array rotated at an unknown pivot, like [4, 5, 6, 7, 0, 1, 2], is no longer globally sorted, but it has a crucial property: for any mid, at least one of the two halves is sorted.

Find Minimum in Rotated Sorted Array (LeetCode 153)

Predicate over indices: nums[i] <= nums[n-1]. Elements in the left (larger) block are greater than the last element; elements in the right block are not. That is F F F T T T, and the minimum is the first true.

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:     # mid is in the left, larger block
            lo = mid + 1
        else:                        # mid is in the right block (could be the min)
            hi = mid
    return nums[lo]

Comparing with nums[hi] rather than nums[lo] is deliberate: it also handles the unrotated case [1, 2, 3] correctly. Comparing against nums[lo] needs an extra special case.

Dry run on [4, 5, 6, 7, 0, 1, 2]: lo 0, hi 6, mid 3 (7 > 2) so lo 4; mid 5 (1 ≤ 2) so hi 5; mid 4 (0 ≤ 1) so hi 4. Return nums[4] = 0.

Search in Rotated Sorted Array (LeetCode 33)

Two valid approaches. Two-phase: find the minimum's index with the code above, decide which sorted block can contain the target, and run a normal binary search there. One-pass: at each step identify the sorted half and check whether the target lies in its range.

int search(const vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {                       // left half sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                           // right half sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

The two-phase version is often easier to get right under pressure, and interviewers accept it. A full array-focused treatment is in array interview patterns.

Duplicates (LeetCode 81 and 154)

With duplicates, nums[lo] == nums[mid] == nums[hi] tells you nothing about which half is sorted (consider [1, 1, 1, 0, 1] and [1, 0, 1, 1, 1]). The fix is to shrink by one (hi -= 1 for find-min, or lo += 1; hi -= 1 for search). Worst-case time becomes O(n), and saying so is part of the expected answer.

Binary Search Without a Sorted Array: Peaks and Matrices

Find Peak Element (LeetCode 162)

The array is not sorted, but the predicate nums[i] > nums[i+1] works as a guide: if nums[mid] < nums[mid+1], there must be a peak to the right (the values rise and the array "ends" in negative infinity), so discard the left.

public int findPeakElement(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < nums[mid + 1]) lo = mid + 1;   // climb uphill
        else hi = mid;
    }
    return lo;
}

Search a 2D Matrix (LeetCode 74)

If each row is sorted and each row starts after the previous row ends, treat the matrix as one sorted array of length m × n and map index k to (k / n, k % n). For row- and column-sorted matrices without that property (LeetCode 240), the staircase walk from the top-right corner in O(m + n) beats binary search.

Median of Two Sorted Arrays

The hardest classic binary search searches the partition point of the shorter array, in O(log min(m, n)). It deserves its own walkthrough: Median of Two Sorted Arrays explained.

Binary Search on Answer: The Pattern Behind "Minimise the Maximum"

Some optimisation problems are hard to solve directly but easy to verify: "Can Koko finish all bananas in h hours at speed s?" is a simple loop. If feasibility is monotonic in the candidate answer, binary search the answer range and call the check O(log R) times.

1. Identify the answer variable (speed, capacity, distance, days, pages).
2. Write feasible(x), usually a greedy O(n) pass.
3. Prove monotonicity in one sentence: "if speed s works, any faster speed also works".
4. Set tight, safe bounds: lo = smallest conceivable answer, hi = an answer guaranteed feasible.
5. Pick the template: minimising means first true; maximising means last true.

Recognition clues: "minimum largest", "maximum smallest", "minimum capacity/speed/time such that", values up to 10⁹ with n up to 10⁵, and a check that is obviously greedy once the answer is fixed.

Koko Eating Bananas (LeetCode 875)

Koko has piles of bananas and h hours. Each hour she picks a pile and eats up to s bananas from it. Find the minimum integer s to finish in time.

Check: hours at speed s = sum of ceil(p / s) over piles. Monotonic: faster never takes longer. Bounds: lo = 1 (not 0, which would divide by zero), hi = max(piles) (at that speed each pile takes one hour, and h ≥ number of piles is guaranteed). Minimising, so first true.

def min_eating_speed(piles, h):
    def hours(s):
        return sum((p + s - 1) // s for p in piles)   # integer ceil

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

int minEatingSpeed(const vector<int>& piles, int h) {
    auto hours = [&](long long s) {
        long long total = 0;                      // can exceed int range
        for (int p : piles) total += (p + s - 1) / s;
        return total;
    };
    long long lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (hours(mid) <= h) hi = mid; else lo = mid + 1;
    }
    return (int)lo;
}

Dry run with piles = [3, 6, 7, 11], h = 8:

Answer 4. Complexity: O(n log max(piles)), about 30 passes over the piles for values up to 10⁹.

Aggressive Cows: Maximise the Minimum Distance

This SPOJ classic (AGGRCOW) is a favourite in Indian interview prep sheets. Given stall positions and C cows, place the cows in stalls so that the minimum distance between any two cows is as large as possible. LeetCode's Magnetic Force Between Two Balls (1552) is the same problem.

Check canPlace(d): sort stalls, put the first cow in the first stall, then greedily put each next cow in the first stall at least d beyond the previous cow. Feasible if you place all C. Greedy is optimal because placing a cow as early as possible never hurts later placements. Monotonic: if gap d is achievable, any smaller gap is too, so feasible answers form a prefix: last true. Bounds: lo = 0 (always feasible), hi = max - min.

#include <algorithm>
#include <vector>
using namespace std;

bool canPlace(const vector<int>& stalls, int cows, int d) {
    int placed = 1, last = stalls[0];
    for (size_t i = 1; i < stalls.size(); ++i) {
        if (stalls[i] - last >= d) {
            if (++placed == cows) return true;
            last = stalls[i];
        }
    }
    return placed >= cows;
}

int aggressiveCows(vector<int> stalls, int cows) {
    sort(stalls.begin(), stalls.end());
    int lo = 0, hi = stalls.back() - stalls.front();
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;       // round up: we assign lo = mid
        if (canPlace(stalls, cows, mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

def aggressive_cows(stalls, cows):
    stalls.sort()

    def can_place(d):
        placed, last = 1, stalls[0]
        for x in stalls[1:]:
            if x - last >= d:
                placed += 1
                last = x
                if placed == cows:
                    return True
        return placed >= cows

    lo, hi = 0, stalls[-1] - stalls[0]
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if can_place(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

Dry run with stalls [1, 2, 4, 8, 9], 3 cows: range [0, 8]. mid 4: place at 1, then 8, can't place a third (needs 12): infeasible, hi = 3. mid 2: 1, 4, 8: feasible, lo = 2. mid 3: 1, 4, 8: feasible, lo = 3. Answer 3.

Book Allocation (and Split Array Largest Sum)

Given page counts of n books in order and m students, assign each student a contiguous block of at least one book so that the maximum pages any student reads is minimised. LeetCode's Split Array Largest Sum (410), Capacity To Ship Packages Within D Days (1011) and the "painter's partition" problem are the same structure.

Check feasible(cap): walk the books, adding pages to the current student until the next book would exceed cap, then start a new student. Feasible if students used ≤ m. Monotonic: a larger cap never needs more students: first true. Bounds: lo = max(pages) (someone must read the biggest book), hi = sum(pages) (one student reads everything). If m > n, return -1 since each student needs a book.

public int allocateBooks(int[] pages, int m) {
    if (m > pages.length) return -1;
    long lo = 0, hi = 0;
    for (int p : pages) { lo = Math.max(lo, p); hi += p; }
    while (lo < hi) {
        long mid = lo + (hi - lo) / 2;
        if (studentsNeeded(pages, mid) <= m) hi = mid;
        else lo = mid + 1;
    }
    return (int) lo;
}

private int studentsNeeded(int[] pages, long cap) {
    int students = 1;
    long load = 0;
    for (int p : pages) {
        if (load + p > cap) { students++; load = p; }
        else load += p;
    }
    return students;
}

Why is "students needed ≤ m" enough when every student must get at least one book? Because with m ≤ n you can always split a multi-book block to hand books to idle students without increasing the maximum. Interviewers sometimes probe that exact point.

Example: pages [12, 34, 67, 90], m = 2. Range [90, 203]. The answer is 113: [12, 34, 67] and [90]. At cap 112 you need three students (12 + 34 = 46, then 67 + 90 would exceed, giving [12, 34], [67], [90]), so 113 is the smallest feasible cap.

More Binary Search on Answer Problems

Binary search on real numbers

When the answer is a real number, loop a fixed number of times (60 to 100 iterations of halving gets below any practical precision) instead of comparing with an epsilon, which can loop forever due to floating-point rounding.

def real_sqrt(x):
    lo, hi = 0.0, max(1.0, x)
    for _ in range(100):
        mid = (lo + hi) / 2
        if mid * mid <= x:
            lo = mid
        else:
            hi = mid
    return lo

Common Binary Search Mistakes in Interviews

• Infinite loop from lo = mid with a rounded-down mid. Use Template B's rounding.
• Integer overflow in lo + hi or inside the check (Koko's total hours, Book Allocation's page sums, mid * mid in sqrt). Use 64-bit types.
• Bad bounds: Koko with lo = 0 divides by zero; Book Allocation with lo = 0 makes the greedy check accept caps smaller than a single book and return nonsense.
• Non-monotonic predicate: if you cannot state the "if x works then x+1 works" sentence, binary search is the wrong tool (or the predicate needs rephrasing).
• Mixing templates: while (lo <= hi) with hi = mid loops forever when lo == hi. Pick one form per problem and stick to its rules.
• Returning the wrong variable after a closed-interval loop: when lo <= hi ends, lo is the insertion point and hi = lo - 1.

How to present it in an interview

Say: "The answer lies between A and B. Given a candidate x, I can check feasibility greedily in O(n). Feasibility is monotonic because a larger x only makes things easier. So I binary search for the smallest feasible x, giving O(n log(B - A))." Then code the check first, test it on one value, and only then wrap it in the template. Interviewers at product companies value that order because the check is where the logic lives. The broader approach is in how to approach a DSA problem.

Binary Search Practice List

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.