Binary Search LeetCode Pattern Guide — Bounds, Rotated Arrays, and Search-on-Answer

A binary search LeetCode pattern guide is less about memorizing mid = left + right // 2 and more about proving which half can be discarded. Binary search works when there is monotonic structure: sorted values, a true/false boundary, or an answer space where feasibility switches from impossible to possible. Bounds, rotated arrays, and search-on-answer problems all use the same discipline. Define the invariant, choose inclusive or half-open bounds, update without losing the answer, and stop when the search space collapses.

Binary search LeetCode pattern guide: the four common shapes

| Problem shape | Target | Typical template | |---|---|---| | Exact search | Find target value or return -1 | Inclusive [lo, hi] | | Lower bound | First index where arr[i] >= target | Half-open [lo, hi) or inclusive answer | | Upper bound | First index where arr[i] > target | Half-open boundary search | | Rotated sorted array | Find target or minimum with one sorted side | Inclusive with side checks | | Search on answer | Minimum capacity/time/rate that works | Feasibility predicate |

The most important sentence in any binary search answer is: "The predicate is monotonic." If that is not true, binary search is a guess, not an algorithm.

Exact search in a sorted array

Exact search is the version everyone learns first. With inclusive bounds:

1. lo = 0, hi = n - 1.
2. While lo <= hi, compute mid.
3. If arr[mid] == target, return mid.
4. If arr[mid] < target, discard left half: lo = mid + 1.
5. Otherwise discard right half: hi = mid - 1.
6. Return -1.

The invariant is that if the target exists, it is inside [lo, hi]. Every update must preserve that invariant. If arr[mid] < target, mid cannot be the answer, so mid + 1 is safe. If arr[mid] > target, mid - 1 is safe.

In languages with fixed-width integers, compute mid = lo + (hi - lo) // 2 to avoid overflow. In Python, overflow is not an issue, but the overflow-safe formula is still a good habit.

Lower bound and upper bound

Lower bound finds the first position where a condition becomes true. For sorted arrays, lower bound for target is the first index i where arr[i] >= target. Upper bound is first index where arr[i] > target.

Half-open lower bound template:

• Search range is [lo, hi).
• lo = 0, hi = n.
• While lo < hi:
• mid = (lo + hi) // 2.
• If arr[mid] >= target, answer may be mid, so hi = mid.
• Else lo = mid + 1.
• Return lo.

This returns an insertion position from 0 to n. If you need to confirm target exists, check lo < n and arr[lo] == target.

Upper bound changes only the predicate to arr[mid] > target. To find the last index equal to target, compute upper_bound(target) - 1 and validate.

The boundary-search mental model is stronger than exact search because many hard problems are really lower bounds over a virtual array of false/true values.

First true / last false

Abstract the lower bound pattern:

False False False True True True

Find the first true. The predicate might be "can ship within D days with capacity x" or "there are at least k numbers less than or equal to x." It does not need to be an array lookup.

For first true:

• If predicate(mid) is true, keep mid and search left: hi = mid.
• If false, discard mid and search right: lo = mid + 1.
• Return lo.

For last false, you can return lo - 1 after first true, or write a symmetric template. Prefer first true unless the prompt naturally asks for the largest feasible value.

The key is setting bounds so the answer is guaranteed inside. For minimum speed, low might be 1 and high might be max pile size. For minimum capacity, low might be max package weight and high might be sum of weights. Good bounds reduce iterations and prevent invalid mid values.

Search-on-answer

Search-on-answer, also called binary search on answer, is the pattern behind Koko Eating Bananas, Capacity to Ship Packages, Split Array Largest Sum, Minimize Maximum Distance, and many scheduling problems.

The structure:

1. Define the answer variable x.
2. Establish a low and high bound for x.
3. Write can(x) that returns true if x is sufficient.
4. Prove monotonicity: if x works, any larger x works; or if x works, any smaller x works for max-style problems.
5. Binary search the boundary.

Example: shipping packages within D days. The answer is minimum ship capacity. Low is the heaviest package because capacity below that is impossible. High is sum of all packages because one day can carry everything. can(capacity) simulates days needed. If capacity works, larger capacity also works, so find first true.

The trap is making can() too slow. If binary search runs log R times and can() is O(n), total is O(n log R), where R is numeric range. That is usually fine. If can() itself sorts or does nested scans, rethink it.

Rotated sorted arrays

A rotated sorted array preserves sorted order in two segments. The challenge is deciding which side is sorted and whether the target lies in it.

Exact target search with unique values:

1. Compute mid.
2. If nums[mid] == target, return mid.
3. If nums[lo] <= nums[mid], the left side is sorted.
4. If target is between nums[lo] and nums[mid], move hi = mid - 1; otherwise lo = mid + 1.
5. Else the right side is sorted.
6. If target is between nums[mid] and nums[hi], move lo = mid + 1; otherwise hi = mid - 1.

The invariant is still that target remains inside the current range. The side checks tell you which half can be reasoned about as sorted.

Finding the minimum in a rotated sorted array is a different boundary problem. Compare nums[mid] with nums[hi]. If nums[mid] > nums[hi], the minimum is to the right of mid. Otherwise the minimum is at mid or left of mid, so hi = mid. Stop at lo == hi.

Duplicates complicate rotation. If nums[mid] == nums[hi], you cannot determine which side contains the minimum, so decrement hi and accept worst-case O(n). Say this explicitly if duplicates are allowed.

Binary search in 2D matrices

There are two common matrix patterns.

If the matrix is globally sorted as if flattened, map 1D mid to coordinates: row = mid // cols, col = mid % cols. Search range is 0 to rows * cols - 1. This is exact binary search.

If each row and column is sorted but the matrix is not globally flattened, use the staircase search from top-right or bottom-left. That is not binary search, but it uses sorted structure. From top-right, if value is too large, move left; if too small, move down. Complexity is O(rows + cols). Do not force binary search when the matrix shape does not support it.

For kth smallest in a sorted matrix, binary search the value range, not indices. Predicate: count how many values are <= mid. If count is at least k, mid may be high enough, so search left. This is search-on-answer with a counting subroutine.

Template choice: inclusive vs half-open

Inclusive [lo, hi] is intuitive for exact search. Half-open [lo, hi) is clean for lower bound. Mixing them creates off-by-one bugs.

A practical rule:

• Use inclusive when you return immediately on equality.
• Use half-open when you are finding a boundary or insertion position.
• Use while lo < hi when the answer remains in the range.
• Use while lo <= hi when the range can become empty.

Do not memorize five templates. Memorize one exact-search template and one first-true template. Derive the rest.

Common traps in binary search

Infinite loop. If mid can equal lo and you set lo = mid, the range may not shrink. Use mid + 1 or biased mid for upper-bound searches.

Lost answer. If mid might be the answer, do not discard it. Set hi = mid, not hi = mid - 1, in first-true half-open search.

Bad bounds. Low and high must include the answer. For capacity problems, low cannot be zero if packages have positive weights.

Non-monotonic predicate. Binary search only works when the answer space has one transition.

Integer division in feasibility. Koko-style problems need ceiling division: (pile + speed - 1) // speed.

Rotated duplicates. Equal boundary values may destroy the ability to choose a side.

Returning unvalidated insertion index. Lower bound returns where target would go, not proof it exists.

Prep checklist for binary search problems

Before coding, write:

• What is being searched: index, value, capacity, time, speed, answer?
• What is the monotonic condition?
• Am I finding exact match, first true, first greater/equal, or minimum feasible?
• What are inclusive/exclusive bounds?
• Can mid itself still be the answer?
• How does the range shrink every iteration?
• What should be returned when target is absent?
• Are duplicates allowed?
• What is the cost of the predicate?

This checklist is faster than debugging off-by-one errors after the fact.

How to explain binary search in interviews and resumes

In an interview, the strongest phrase is "I can define a monotonic predicate." For shipping capacity: "For a given capacity, I can test whether all packages ship within D days. If capacity works, any larger capacity also works, so I will binary search the first capacity that works." That explanation proves the algorithm.

For rotated arrays: "At least one side of the midpoint is sorted. I will determine the sorted side and check whether the target falls within that side's bounds. If not, it must be in the other half." That is better than reciting code.

On a resume, binary search is usually hidden inside optimization language:

• "Reduced configuration search time by binary-searching the minimum feasible threshold against a simulation predicate."
• "Built sorted-index lookup with lower-bound semantics for range queries."
• "Optimized capacity planning tool by replacing linear scans with monotonic boundary search."

The pattern is powerful because it turns a large answer space into a handful of feasibility checks. If you can define the boundary precisely, binary search becomes a proof, not a trick.

A quick practice ladder

Work through binary search in this order. First, implement exact search until the inclusive bounds feel automatic. Second, implement lower bound and upper bound on arrays with duplicates, because duplicate handling is where most off-by-one errors hide. Third, solve one rotated-array target problem and one rotated-array minimum problem so you learn the difference between value search and pivot search. Fourth, do three search-on-answer prompts with different predicates: minimum eating speed, minimum ship capacity, and split array largest sum. After each problem, write the predicate in plain English before writing code.

A useful self-test: cover the code and explain why lo moves, why hi moves, and whether mid can still be the answer. If you cannot answer those three questions, the template is carrying you instead of the invariant. Binary search becomes reliable when the invariant is stronger than your memory of the code.

Related guides

• Trie LeetCode Pattern Guide — Prefix Search, Autocomplete, and Word Problems — A practical trie pattern guide for LeetCode interviews: when prefix trees beat hash sets, how to code the templates, and how to handle autocomplete, wildcard search, and board word problems.
• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.
• BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source — A BFS LeetCode pattern guide for recognizing queue-based problems, implementing level-order traversal, solving unweighted shortest paths, using multi-source BFS, and avoiding common visited-state bugs.
• Bit Manipulation LeetCode Pattern Guide — XOR Tricks, Masks, and Counting Bits — A practical bit manipulation LeetCode pattern guide covering XOR tricks, masks, counting bits, subset enumeration, flags, and the interview pitfalls around signed integers.
• DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.