Advanced Binary Search Interview Patterns
Binary search is not just “is target in sorted array.” The real interview value comes from recognizing when to binary search on the answer space rather than the array index, and from applying a universal predicate-based template that handles all variants without off-by-one errors.
Classic Template Review
def binary_search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # avoids overflow vs (left+right)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Key points: use left + (right - left) // 2 to avoid integer overflow (critical in Java/C++; in Python it does not matter but the habit is good). Loop condition left <= right means we exit when the search space is empty – there is no unchecked element left.
Binary Search on Answer Space
The most powerful generalization: instead of searching for a value in an array, you binary search on the possible answers to the problem. Define a predicate feasible(x) that returns True if x is a valid answer. The predicate is monotone: there exists a threshold T such that feasible(x) is False for x < T and True for x >= T. Binary search finds T.
# LC 1011 - Minimum Capacity to Ship Packages in D Days
def shipWithinDays(weights: list[int], days: int) -> int:
def feasible(capacity: int) -> bool:
current_load, day_count = 0, 1
for w in weights:
if current_load + w > capacity:
day_count += 1
current_load = 0
current_load += w
return day_count <= days
lo = max(weights) # must carry heaviest package in one trip
hi = sum(weights) # carry everything in one day
while lo int:
def feasible(speed: int) -> bool:
import math
return sum(math.ceil(p / speed) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
Notice both problems use the exact same outer template. The only difference is the feasible() function. When you see “minimize the maximum” or “maximize the minimum” or “find the smallest X such that condition holds,” think binary search on answer space.
Find Minimum in Rotated Sorted Array (LC 153)
After rotation, the array has two sorted halves. Compare mid with the rightmost element: if nums[mid] > nums[right], the minimum is in the right half (mid is in the higher left segment). Otherwise, the minimum is in the left half including mid.
def findMin(nums: list[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo nums[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # min is at mid or in left half
return nums[lo]
Why compare with nums[hi] rather than nums[lo]? Because the pivot (minimum) breaks the invariant relative to the left bound but maintains it relative to the right bound. The right side is always in the unsegmented portion from the minimum’s perspective.
Search in Rotated Sorted Array (LC 33)
One of the two halves around mid is always sorted. Check which half is sorted, then check if the target falls within that sorted half. If yes, search that half. If no, search the other half.
def search(nums: list[int], target: int) -> int:
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
Find Peak Element (LC 162)
A peak element is greater than its neighbors. If nums[mid] < nums[mid+1], the slope is rising to the right – there must be a peak in the right half. Otherwise, the slope is falling (or mid is a peak) – search the left half including mid.
def findPeakElement(nums: list[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # ascending slope, peak is right
else:
hi = mid # descending slope, peak is at mid or left
return lo
Search in 2D Matrix: LC 74 vs LC 240
These two problems look identical but require different approaches:
LC 74 – rows are sorted and the first element of each row is greater than the last of the previous row. The matrix is effectively a flattened sorted array. Treat it as 1D with index arithmetic.
# LC 74 - matrix[row][col] is strictly 1D-sorted
def searchMatrix(matrix: list[list[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
lo, hi = 0, m * n - 1
while lo <= hi:
mid = (lo + hi) // 2
val = matrix[mid // n][mid % n]
if val == target:
return True
elif val bool:
row, col = 0, len(matrix[0]) - 1
while row = 0:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
col -= 1 # eliminate this column
else:
row += 1 # eliminate this row
return False
LC 240’s top-right approach is O(m + n), not O(log(mn)). It is not binary search but the same divide-and-eliminate thinking.
Count of Smaller Numbers After Self (LC 315)
Process elements right to left. Maintain a sorted list of seen elements. For each new element, binary search the sorted list to find how many elements are smaller (this is its insertion index). Insert the element into the sorted list. Using Python’s bisect module and sortedcontainers.SortedList, this is O(n log n).
import bisect
def countSmaller(nums: list[int]) -> list[int]:
sorted_seen = []
result = []
for num in reversed(nums):
pos = bisect.bisect_left(sorted_seen, num)
result.append(pos)
bisect.insort(sorted_seen, num)
return result[::-1]
Note: bisect.insort is O(n) due to list shifting. For a true O(n log n) solution, use a Binary Indexed Tree (Fenwick Tree) or segment tree with coordinate compression.
Universal Predicate-Based Template
Every binary search problem can be expressed as: find the leftmost position where predicate P(x) is True, given that the predicate transitions from False to True exactly once.
def binary_search_template(lo: int, hi: int, pred) -> int:
"""
Find the smallest value in [lo, hi] for which pred returns True.
Assumes pred is monotone: False...False, True...True.
Returns lo if pred(lo) is True, returns hi+1 if pred is never True.
"""
while lo = target:
# binary_search_template(0, len(nums)-1, lambda i: nums[i] >= target)
#
# Find minimum capacity for shipping problem:
# binary_search_template(max(weights), sum(weights), feasible)
Off-by-One Errors: The Decision Guide
| Situation | Loop condition | Return value | Notes |
|---|---|---|---|
| Find exact value (may not exist) | lo <= hi | mid (or -1) | Exit when lo > hi means no element left to check |
| Find leftmost True in predicate | lo < hi | lo | lo == hi is the convergence point |
| Find rightmost False in predicate | lo < hi | lo – 1 | lo is first True, so lo-1 is last False |
| Find minimum in rotated array | lo < hi | lo | hi = mid (not mid-1) to preserve the answer |
| Find peak element | lo < hi | lo | Same pattern as minimum |
The safe default: Use the predicate template (lo < hi, return lo) for all “find the boundary” problems. Use lo <= hi only when you are explicitly searching for a specific value that may or may not exist.
Common mistake: Using hi = mid - 1 when the answer could be mid itself (causes the algorithm to skip the correct answer). In the predicate template, when pred(mid) is True, set hi = mid (not mid - 1) because mid is a valid candidate that should not be eliminated.
Meta coding interviews test advanced binary search patterns. See common questions for Meta interview: binary search and search algorithm problems.
Uber algorithm interviews include binary search on answer space problems. See patterns for Uber interview: binary search and optimization problems.
Apple coding rounds include binary search and sorted array manipulation. See patterns for Apple interview: binary search and sorted array problems.