Binary Search Variants
Once you understand basic binary search, a huge class of LeetCode Medium and Hard problems becomes approachable — because they all reduce to binary search with a different "condition function."
This page covers the most important variants: finding boundaries in sorted arrays, searching 2D matrices, finding peaks, and binary search on the answer (a technique where you binary search over possible answers rather than array indices).
Lower Bound and Upper Bound
lower_bound: the index of the first element ≥ target (C++ std::lower_bound). upper_bound: the index of the first element > target (C++ std::upper_bound).
Together, they give you the range of indices where target appears: [lower_bound, upper_bound).
// First index where arr[i] >= target
function lowerBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
// First index where arr[i] > target
function upperBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] <= target) lo = mid + 1; // only difference: <= instead of <
else hi = mid;
}
return lo;
}
const arr = [1, 2, 2, 2, 3, 5];
lowerBound(arr, 2); // → 1 (arr[1] = 2, first occurrence)
upperBound(arr, 2); // → 4 (arr[4] = 3, first element > 2)
// Target 2 appears at indices [1, 4) = indices 1, 2, 3
lowerBound(arr, 4); // → 5 (would insert between 3 and 5)
upperBound(arr, 4); // → 5 (same — 4 is not present)
// Count occurrences of target in sorted array
function countOccurrences(arr, target) {
return upperBound(arr, target) - lowerBound(arr, target);
}
countOccurrences(arr, 2); // → 4 - 1 = 3lowerBound([1,2,2,2,3,5], 2) → 1 upperBound([1,2,2,2,3,5], 2) → 4 countOccurrences([1,2,2,2,3,5], 2) → 3
First and Last Occurrence
// LeetCode 34 — Find First and Last Position of Element in Sorted Array
function searchRange(nums, target) {
const first = lowerBound(nums, target);
if (first === nums.length || nums[first] !== target) return [-1, -1];
const last = upperBound(nums, target) - 1;
return [first, last];
}
function lowerBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
function upperBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] <= target) lo = mid + 1;
else hi = mid;
}
return lo;
}
searchRange([5,7,7,8,8,10], 8); // → [3, 4]
searchRange([5,7,7,8,8,10], 6); // → [-1, -1]Search a 2D Matrix
A matrix where each row is sorted and the first element of each row is greater than the last element of the previous row. This can be treated as a single sorted array of size m×n.
// LeetCode 74 — Search a 2D Matrix
// Matrix is "fully sorted" — treat as flattened sorted array
function searchMatrix(matrix, target) {
const m = matrix.length, n = matrix[0].length;
let lo = 0, hi = m * n - 1;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
// Convert flat index to 2D coordinates
const val = matrix[Math.floor(mid / n)][mid % n];
if (val === target) return true;
if (val < target) lo = mid + 1;
else hi = mid - 1;
}
return false;
}
// Example matrix:
// [[ 1, 3, 5, 7],
// [10, 11, 16, 20],
// [23, 30, 34, 60]]
const matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]];
searchMatrix(matrix, 3); // → true
searchMatrix(matrix, 13); // → falseFind Peak Element
A peak element is one that is strictly greater than its neighbors. The array may have multiple peaks — return the index of any one of them.
Key insight: if arr[mid] < arr[mid+1], there must be a peak to the right of mid. Otherwise, there is a peak at mid or to the left.
// LeetCode 162 — Find Peak Element
function findPeakElement(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] < nums[mid + 1]) {
lo = mid + 1; // peak is to the right
} else {
hi = mid; // peak is at mid or to the left
}
}
return lo; // lo === hi: the peak
}
findPeakElement([1, 2, 3, 1]); // → 2 (nums[2] = 3)
findPeakElement([1, 2, 1, 3, 5, 6, 4]); // → 5 (nums[5] = 6)
// Why this works: the array boundaries are treated as -∞,
// so a peak must exist. At each step, we move toward the higher neighbor.Minimum in Rotated Sorted Array
// LeetCode 153 — Find Minimum in Rotated Sorted Array (no duplicates)
function findMin(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (nums[mid] > nums[hi]) {
// mid is in the left (larger) part — minimum is to the right
lo = mid + 1;
} else {
// mid is in the right (smaller) part — minimum is at mid or left
hi = mid;
}
}
return nums[lo];
}
findMin([3, 4, 5, 1, 2]); // → 1
findMin([4, 5, 6, 7, 0, 1, 2]); // → 0
findMin([11, 13, 15, 17]); // → 11 (not rotated)Binary Search on the Answer
This is the most powerful binary search pattern. Instead of searching for a value in an array, you binary search over the space of possible answers to find the minimum or maximum that satisfies some condition.
The technique works whenever:
- You can define a condition function f(x) that answers "is x a valid answer?"
- The condition is monotonic: if x is valid, all larger (or all smaller) values are also valid
Problem: Koko Eating Bananas (LeetCode 875) Koko has n piles of bananas. She must eat all bananas in h hours. Find the minimum eating speed k (bananas/hour) that lets her finish in time.
function minEatingSpeed(piles, h) {
// Condition: can Koko eat all bananas at speed k within h hours?
function canFinish(k) {
let hours = 0;
for (const pile of piles) {
hours += Math.ceil(pile / k); // hours needed for this pile at speed k
}
return hours <= h;
}
// Binary search on the answer: minimum valid k
// k ranges from 1 to max(piles)
let lo = 1, hi = Math.max(...piles);
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (canFinish(mid)) hi = mid; // mid works, try smaller
else lo = mid + 1; // mid too slow, need faster
}
return lo;
}
// piles = [3,6,7,11], h = 8
minEatingSpeed([3,6,7,11], 8); // → 4
// At k=4: ceil(3/4)=1 + ceil(6/4)=2 + ceil(7/4)=2 + ceil(11/4)=3 = 8 hours ✓
// At k=3: ceil(3/3)=1 + ceil(6/3)=2 + ceil(7/3)=3 + ceil(11/3)=4 = 10 hours ✗minEatingSpeed([3,6,7,11], 8) → 4
Problem: Capacity to Ship Packages (LeetCode 1011) Ship packages in D days. Find minimum weight capacity of the ship.
function shipWithinDays(weights, days) {
// Condition: can we ship all packages with capacity cap in 'days' days?
function canShip(cap) {
let daysNeeded = 1, currentLoad = 0;
for (const w of weights) {
if (currentLoad + w > cap) {
daysNeeded++; // start a new day
currentLoad = 0;
}
currentLoad += w;
}
return daysNeeded <= days;
}
// lo = max single weight (must carry heaviest package)
// hi = sum of all weights (ship everything in one day)
let lo = Math.max(...weights), hi = weights.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (canShip(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5); // → 15Problem: Split Array Largest Sum (LeetCode 410) Split array into k subarrays to minimize the maximum subarray sum.
function splitArray(nums, k) {
// Condition: can we split into k pieces where each piece sum <= maxSum?
function canSplit(maxSum) {
let pieces = 1, currentSum = 0;
for (const num of nums) {
if (currentSum + num > maxSum) {
pieces++;
currentSum = 0;
}
currentSum += num;
}
return pieces <= k;
}
let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (canSplit(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}
splitArray([7, 2, 5, 10, 8], 2); // → 18 ([7,2,5] and [10,8], max sum = 18)The Pattern for Binary Search on Answer
// Template for "find minimum x such that f(x) is true"
function findMinAnswer(lo, hi, condition) {
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (condition(mid)) hi = mid; // mid is valid, try smaller
else lo = mid + 1; // mid is invalid, try larger
}
return lo; // minimum valid answer
}
// Template for "find maximum x such that f(x) is true"
function findMaxAnswer(lo, hi, condition) {
while (lo < hi) {
const mid = lo + Math.floor((hi - lo + 1) / 2); // NOTE: +1 to bias upward (prevents infinite loop)
if (condition(mid)) lo = mid; // mid is valid, try larger
else hi = mid - 1; // mid is invalid, try smaller
}
return lo; // maximum valid answer
}
// Key steps to apply this pattern:
// 1. Define the search space [lo, hi] for possible answers
// 2. Write condition(x): "is x a valid answer?"
// 3. Verify the condition is monotonic (once true, stays true)
// 4. Apply the correct template (minimize or maximize)Koko Eating Bananas — minimize speed: binary search on [1, max(piles)]
Capacity to Ship — minimize capacity: binary search on [max(w), sum(w)]
Split Array Largest Sum — minimize max sum: binary search on [max(nums), sum(nums)]
Minimum Number of Days to Make m Bouquets — binary search on days [1, max_bloom_day]
Find the Smallest Divisor — binary search on divisor [1, max(nums)]
Magnetic Force Between Balls — maximize minimum distance: binary search on distance