Apply binary search beyond simple sorted arrays — rotated arrays, search spaces, and answer-based searching.
Standard binary search finds a target in a sorted array in O(log n) time by repeatedly halving the search space. Modified binary search adapts this same halving technique to problems where the search space is not a simple sorted array — rotated arrays, partially sorted data, or even abstract numeric ranges where you search for the optimal answer.
Maintain two pointers, lo and hi, that bound the search space. Compute mid, evaluate a condition, then discard half the space. Repeat until the answer is found.
The power of halving: Each iteration eliminates half the remaining candidates. For n = 1,000,000 elements, binary search needs at most 20 comparisons. Linear search would need up to 1,000,000.
Look for these recognition signals in the problem statement. If you spot one or more, modified binary search is very likely the intended approach.
"Sorted or partially sorted array"
"Find the minimum/maximum that satisfies..."
"Monotonic predicate"
"Search space can be halved"
Not just arrays! Binary search works on any search space where you can evaluate a predicate at a midpoint and discard one half. This includes abstract numeric ranges (e.g., "what is the minimum speed?"), not just physical arrays.
The classic template. Search for an exact target in a sorted array. Return its index, or -1 if not found. The loop uses lo <= hi because a single element (lo == hi) is still a valid candidate.
int binarySearch(int[] arr, int target) { int lo = 0, hi = arr.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; // avoids overflow if (arr[mid] == target) return mid; else if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; } return -1; // not found }
Found target 9 at index 4 in just 3 iterations out of 7 elements.
When duplicates exist, the standard template returns any matching index. To find the leftmost or rightmost occurrence, we change the loop condition to lo < hi and avoid returning early when we find a match — instead, we continue searching to tighten the bound.
// Returns index of first element >= target int lo = 0, hi = arr.length - 1; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] < target) lo = mid + 1; else hi = mid; // don't skip mid — it might be the answer } // lo == hi == index of first occurrence (if it exists)
// Returns index of last element <= target int lo = 0, hi = arr.length - 1; while (lo < hi) { int mid = lo + (hi - lo + 1) / 2; // round UP to avoid infinite loop if (arr[mid] > target) hi = mid - 1; else lo = mid; // don't skip mid — it might be the answer } // lo == hi == index of last occurrence (if it exists)
First occurrence of 5 is at index 2. The key: when arr[mid] == target, we set hi = mid (not return mid) to keep searching left.
Round-up trick for last occurrence: When lo = mid is possible, use mid = lo + (hi - lo + 1) / 2 (rounding up). Otherwise, when lo == mid and the else branch sets lo = mid, the loop never terminates.
A sorted array has been rotated at an unknown pivot. For example, [0,1,2,4,5,6,7] becomes [4,5,6,7,0,1,2]. The key insight: at least one half around mid is always sorted. Determine which half is sorted, then check if the target falls within that sorted half.
The array has two sorted segments separated by a break where the values drop.
int searchRotated(int[] arr, int target) { int lo = 0, hi = arr.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] == target) return mid; if (arr[lo] <= arr[mid]) { // Left half [lo..mid] is sorted if (arr[lo] <= target && target < arr[mid]) hi = mid - 1; // target in sorted left half else lo = mid + 1; // target in right half } else { // Right half [mid..hi] is sorted if (arr[mid] < target && target <= arr[hi]) lo = mid + 1; // target in sorted right half else hi = mid - 1; // target in left half } } return -1; }
Found target 0 at index 4 in 3 iterations. At each step, we identified which half was sorted and checked if the target could be there.
Why does arr[lo] <= arr[mid] work? In a rotated array, the rotation break falls in exactly one half. If arr[lo] <= arr[mid], the break is not in the left half, so the left half is properly sorted. Otherwise, the right half from mid to hi is sorted.
Instead of searching through an array, search through the answer space. Define a range [lo, hi] of possible answers, then use a feasibility predicate to halve the range. This technique is extremely powerful for optimization problems.
Packages have weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Ship in 5 days. What is the minimum ship capacity?
int shipWithinDays(int[] weights, int days) { int lo = 0, hi = 0; for (int w : weights) { lo = Math.max(lo, w); // min capacity = heaviest package hi += w; // max capacity = total weight } while (lo < hi) { int mid = lo + (hi - lo) / 2; if (feasible(weights, mid, days)) hi = mid; // can do it — try smaller else lo = mid + 1; // cannot do it — need bigger } return lo; } boolean feasible(int[] weights, int capacity, int days) { int dayCount = 1, currentLoad = 0; for (int w : weights) { if (currentLoad + w > capacity) { dayCount++; currentLoad = 0; } currentLoad += w; } return dayCount <= days; }
The monotonic property: If capacity X works (feasible), then any capacity > X also works. If capacity X does not work, then no capacity < X works either. This monotonicity is what makes binary search valid here.
These four templates cover the vast majority of binary search problems. Memorize the differences in loop conditions and pointer updates.
// Find exact target in sorted array. Returns index or -1. int lo = 0, hi = arr.length - 1; while (lo <= hi) { // <= because single element is valid int mid = lo + (hi - lo) / 2; if (arr[mid] == target) return mid; // found — return immediately else if (arr[mid] < target) lo = mid + 1; else hi = mid - 1; }
// Find leftmost position where arr[i] >= target int lo = 0, hi = arr.length - 1; while (lo < hi) { // < because lo == hi is the answer int mid = lo + (hi - lo) / 2; if (arr[mid] < target) lo = mid + 1; else hi = mid; // keep mid — it might be the first }
// Search for target in a rotated sorted array int lo = 0, hi = arr.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] == target) return mid; if (arr[lo] <= arr[mid]) { // left half is sorted if (arr[lo] <= target && target < arr[mid]) hi = mid - 1; else lo = mid + 1; } else { // right half is sorted if (arr[mid] < target && target <= arr[hi]) lo = mid + 1; else hi = mid - 1; } }
// Find minimum value in [lo, hi] that satisfies a predicate int lo = minPossible, hi = maxPossible; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (feasible(mid)) hi = mid; // feasible — try smaller else lo = mid + 1; // not feasible — need larger } // lo == hi == minimum feasible answer
Choosing the right template: Use lo <= hi when you want an exact match and return inside the loop. Use lo < hi when you want the boundary (first/last/minimum feasible) and the answer is at lo == hi after the loop.
These classic LeetCode problems use modified binary search. They are listed in rough order from fundamental to advanced.
Practice path: Start with #704 (pure binary search) and #35 (lower bound). Then tackle #34 (two binary searches on one array). Once comfortable, try #33 (rotated) and finally #1011 (search on answer) which tests whether you can construct a feasibility predicate.
Step through binary search visually. Watch how the search space shrinks by half at each iteration.
Each iteration halves the search space. Starting with n candidates, after 1 step we have n/2, after 2 steps n/4, and after k steps n/2^k. The loop ends when n/2^k = 1, giving k = log2(n) iterations.
Binary search on answer: The time is O(log(range) * C) where range = hi - lo and C is the cost of the feasibility check. For the shipping problem, C = O(n), so total is O(n * log(sum)).
Space: All variants use O(1) extra space — just a few integer variables for lo, hi, and mid.
Practical impact: For n = 10^9, binary search needs only about 30 iterations. This is why binary search on answer can handle enormous ranges efficiently — the log factor compresses the search space dramatically.
Use lo + (hi - lo) / 2 instead of (lo + hi) / 2. The latter can cause integer overflow when lo and hi are large. The former always produces a valid midpoint. This is a standard interview expectation.
Choose your while condition deliberately. Use lo <= hi for exact-match searches where you return inside the loop. Use lo < hi for boundary searches where the answer is at the convergence point lo == hi.
Identify the monotonic property. Binary search requires that some property changes from false to true (or vice versa) exactly once across the search space. Finding this "transition boundary" is the key to formulating any binary search problem.
Binary search on answer is a meta-technique. Whenever a problem asks "find the minimum X such that...", check if the feasibility predicate is monotonic. If yes, binary search on the answer space and run the feasibility check at each midpoint.
Watch for off-by-one errors. The most common bugs in binary search: wrong loop condition, forgetting to include/exclude mid, and infinite loops from lo = mid without rounding up. Always trace through a 2-element array to verify your template.