Binary Search Variants
Standard binary search on a sorted array is a warmup. The real interview questions twist it: search in a rotated array, find the boundary between true and false, locate a peak, or binary search on the answer space rather than the input. The pattern is always the same — eliminate half the search space each step — but the condition for which half to eliminate changes. That condition is where candidates get tripped up.
The Standard Template
Before tackling variants, lock in the standard template. There are two common styles, and using the wrong one causes off-by-one bugs that cost interviews.
Style 1: left <= right (Inclusive)
function binarySearch(arr, target):
left = 0
right = arr.length - 1
while left <= right:
mid = left + (right - left) / 2 // avoid overflow
if arr[mid] == target:
return mid
else if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
This style works when you are looking for an exact match. The search space is [left, right] inclusive. When left > right, the space is empty and you are done.
Style 2: left < right (Boundary Finding)
function findBoundary(arr, condition):
left = 0
right = arr.length - 1
while left < right:
mid = left + (right - left) / 2
if condition(arr[mid]):
right = mid // mid could be the answer
else:
left = mid + 1 // mid is definitely not the answer
return left // left == right, the boundary
This style is for finding the first element that satisfies a condition (or the last that does not). The search space is [left, right] and it converges until left == right. This is the more versatile template and the one you should reach for in most variant problems.
When to Use Which
Looking for exact value? -> left <= right
Finding first/last with property? -> left < right
Minimizing/maximizing answer? -> left < right
Variant 1: Search in Rotated Sorted Array
A sorted array has been rotated at some pivot. Find a target value. Example: [4, 5, 6, 7, 0, 1, 2], target = 0.
The key insight: at least one half of the array around mid is always sorted. Check which half is sorted, then determine if the target lies in that sorted half.
function searchRotated(arr, target):
left = 0
right = arr.length - 1
while left <= right:
mid = left + (right - left) / 2
if arr[mid] == target:
return mid
// left half is sorted
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
// right half is sorted
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
Walk through the example:
arr = [4, 5, 6, 7, 0, 1, 2], target = 0
left=0, right=6, mid=3, arr[mid]=7
Left half [4,5,6,7] is sorted. 0 not in [4,7). Go right.
left=4, right=6, mid=5, arr[mid]=1
Left half [0,1] is sorted. 0 in [0,1). Go left.
left=4, right=4, mid=4, arr[mid]=0. Found.
With duplicates, this breaks because arr[left] == arr[mid] does not tell you which side is sorted. The fix: when arr[left] == arr[mid], just do left++. This degrades worst case to O(n), but no better solution exists with duplicates.
Variant 2: Find Peak Element
An array where no two adjacent elements are equal. Find any element that is greater than its neighbors.
function findPeak(arr):
left = 0
right = arr.length - 1
while left < right:
mid = left + (right - left) / 2
if arr[mid] < arr[mid + 1]:
left = mid + 1 // peak is to the right
else:
right = mid // peak is at mid or to the left
return left
Why this works: if arr[mid] < arr[mid+1], the slope is going up, so there must be a peak to the right (or mid+1 is the peak). If arr[mid] > arr[mid+1], the slope is going down, so there must be a peak to the left (or mid is the peak). The boundary-finding template handles this perfectly.
Variant 3: First Bad Version
Versions 1 through n. Some version is bad, and all versions after it are bad. Find the first bad version.
function firstBadVersion(n):
left = 1
right = n
while left < right:
mid = left + (right - left) / 2
if isBad(mid):
right = mid // mid could be first bad
else:
left = mid + 1 // mid is good, first bad is after
return left
This is the purest form of the boundary-finding template. The array is conceptually [good, good, good, bad, bad, bad]. You are finding the first "bad." Minimize API calls by always halving the space.
Variant 4: 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. Find a target.
function searchMatrix(matrix, target):
rows = matrix.length
cols = matrix[0].length
left = 0
right = rows * cols - 1
while left <= right:
mid = left + (right - left) / 2
row = mid / cols
col = mid % cols
value = matrix[row][col]
if value == target:
return true
else if value < target:
left = mid + 1
else:
right = mid - 1
return false
The insight: treat the 2D matrix as a flattened 1D sorted array. Map index to (row, col) using division and modulo. Standard binary search from there.
If rows are sorted but the first element of a row is not necessarily greater than the last element of the previous row, you need a different approach: binary search on the row, then binary search within the row. Or use the staircase search (start from top-right corner, go left if too big, go down if too small) which runs in O(m + n).
Variant 5: Median of Two Sorted Arrays
Given two sorted arrays, find the median of the combined sorted array in O(log(min(m, n))).
This is a hard problem. The idea: binary search on where to partition the smaller array, then compute where the larger array must be partitioned.
function findMedian(nums1, nums2):
if nums1.length > nums2.length:
swap(nums1, nums2) // ensure binary search on shorter array
m = nums1.length
n = nums2.length
left = 0
right = m
while left <= right:
i = left + (right - left) / 2 // partition point in nums1
j = (m + n + 1) / 2 - i // partition point in nums2
leftMax1 = nums1[i-1] if i > 0 else -infinity
rightMin1 = nums1[i] if i < m else +infinity
leftMax2 = nums2[j-1] if j > 0 else -infinity
rightMin2 = nums2[j] if j < n else +infinity
if leftMax1 <= rightMin2 and leftMax2 <= rightMin1:
// correct partition
if (m + n) is odd:
return max(leftMax1, leftMax2)
else:
return (max(leftMax1, leftMax2) + min(rightMin1, rightMin2)) / 2
else if leftMax1 > rightMin2:
right = i - 1
else:
left = i + 1
The partition is correct when everything on the left side is smaller than everything on the right side. Binary search adjusts the partition in nums1 until this holds. Binary search on the smaller array keeps it O(log(min(m, n))).
This problem is worth practicing multiple times. It is the hardest binary search variant you will see in interviews and it tests whether you truly understand what binary search is doing at a conceptual level.
Binary Search on the Answer Space
Sometimes you do not binary search the input. You binary search the answer. This is common in optimization problems.
Example: Koko Eating Bananas
Koko has piles of bananas and h hours to eat them all. She picks an eating speed k (bananas per hour). Each pile takes ceil(pile/k) hours. Find the minimum k.
function minEatingSpeed(piles, h):
left = 1
right = max(piles)
while left < right:
mid = left + (right - left) / 2
hours = sum(ceil(pile / mid) for pile in piles)
if hours <= h:
right = mid // can eat slower, try smaller k
else:
left = mid + 1 // too slow, need faster k
return left
You are not searching through piles. You are searching through possible speeds [1, max(piles)]. For each candidate speed, check if it is feasible. The feasibility check is monotonic (if speed k works, speed k+1 also works), which is what makes binary search applicable.
Other "binary search the answer" problems: split array largest sum, capacity to ship packages within d days, magnetic force between balls.
Recognizing Answer-Space Binary Search
Look for:
- "Minimize the maximum" or "maximize the minimum"
- A feasibility function that is monotonic
- A bounded answer range you can search
The Left-Biased vs Right-Biased Trap
When using left < right, the mid calculation determines bias:
left-biased: mid = left + (right - left) / 2 // rounds down
right-biased: mid = left + (right - left + 1) / 2 // rounds up
If you set left = mid (not mid + 1), you must use right-biased mid to avoid infinite loops. If you set right = mid (not mid - 1), use left-biased mid. The safe rule:
If update is left = mid + 1 / right = mid: use floor mid (standard)
If update is left = mid / right = mid - 1: use ceil mid
Getting this wrong causes infinite loops when left + 1 == right. This is the single most common binary search bug.
Common Pitfalls
- Integer overflow in mid calculation. Never use (left + right) / 2. Use left + (right - left) / 2. In languages with fixed-width integers, left + right can overflow.
- Infinite loops with left < right. If you write left = mid without using ceiling division for mid, you loop forever when left + 1 == right. Always trace through the two-element case.
- Wrong comparison in rotated array. Use arr[left] <= arr[mid], not arr[left] < arr[mid]. The equality matters when left == mid (small arrays).
- Forgetting edge cases. Empty array, single element, target smaller than all elements, target larger than all elements. Binary search has more edge cases than most algorithms.
- Applying binary search when the space is not monotonic. Binary search requires that the search space can be divided into two halves with a clear property boundary. If the property is not monotonic, binary search gives wrong answers.
- Not clarifying duplicates. "Find the first occurrence of target" and "find any occurrence of target" require different approaches. Ask the interviewer.
Key Takeaways
- Master two templates: left <= right for exact match, left < right for boundary finding. Do not mix them.
- Every binary search variant reduces to: "which half can I safely discard?" Define that condition clearly before coding.
- Binary search on the answer space is a powerful pattern that many candidates miss. If the problem asks to minimize or maximize something and you can check feasibility, binary search the answer.
- The median of two sorted arrays is the hardest variant. Practice it until the partition logic is second nature. It is a legitimate O(log n) interview question at top companies.
- Always trace through small examples (2-3 elements) to catch off-by-one errors. Binary search bugs are subtle and hard to find by staring at code.
- In the interview, explicitly state your loop invariant. "At every step, the answer is in [left, right]" is a powerful thing to say. It shows rigor and helps you catch errors.