Advanced Binary Search Interview Patterns
Binary search goes far beyond searching a sorted array. The key insight: whenever you can define a monotonic predicate — a condition that switches from false to true (or true to false) exactly once — binary search applies. This unlocks “binary search on the answer” for optimization problems.
Template: Left-Most True (Lower Bound)
def binary_search(lo, hi, condition):
"""Find leftmost position where condition(mid) is True."""
while lo < hi:
mid = lo + (hi - lo) // 2
if condition(mid):
hi = mid # mid might be the answer; search left
else:
lo = mid + 1 # mid is definitely wrong; search right
return lo # lo == hi == answer
Pattern 1: Search in Rotated Sorted Array
The array has two sorted halves. Determine which half is sorted, then check if target is in that half.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# Find minimum in rotated sorted array
def find_min_rotated(nums):
lo, hi = 0, len(nums) - 1
while lo nums[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # mid might be minimum
return nums[lo]
Pattern 2: Binary Search on 2D Matrix
# Search in row+column sorted matrix (rows sorted, col 0 of row i > last of row i-1)
def search_matrix(matrix, target):
rows, cols = len(matrix), len(matrix[0])
lo, hi = 0, rows * cols - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
val = matrix[mid // cols][mid % cols]
if val == target: return True
elif val < target: lo = mid + 1
else: hi = mid - 1
return False
# Search in row-sorted, column-sorted matrix (staircase search — not binary search)
def search_matrix_ii(matrix, target):
r, c = 0, len(matrix[0]) - 1
while r = 0:
if matrix[r][c] == target: return True
elif matrix[r][c] > target: c -= 1
else: r += 1
return False
Pattern 3: Binary Search on the Answer (Optimization)
Instead of searching for a value in an array, search for the answer to an optimization problem. Define a feasibility function and binary search over the solution space.
# Koko Eating Bananas: min speed k to eat all piles in H hours
def min_eating_speed(piles, h):
def can_finish(speed):
return sum((p + speed - 1) // speed for p in piles) <= h
lo, hi = 1, max(piles)
while lo capacity:
needed += 1
cur = 0
cur += w
return needed <= days
lo, hi = max(weights), sum(weights)
while lo max_sum:
parts += 1
cur = 0
cur += n
return parts <= k
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_split(mid): hi = mid
else: lo = mid + 1
return lo
Pattern 4: Find Peak Element
def find_peak(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < nums[mid + 1]:
lo = mid + 1 # ascending, peak is to right
else:
hi = mid # descending or at peak
return lo
Binary Search Problem Classification
| Problem Type | Search Space | Feasibility Check |
|---|---|---|
| Rotated array search | Array indices | Which half is sorted? |
| First bad version | Version numbers | isBadVersion(mid) |
| Koko / ship packages | min…max of input | Can complete in limit? |
| Split array / painter | max…sum of input | Can split into k parts? |
| Sqrt(x) | 0…x | mid*mid <= x |
| Find peak element | Array indices | nums[mid] < nums[mid+1] |
Interview Tips
- Always use
mid = lo + (hi - lo) // 2to avoid integer overflow (important in Java/C++) - Decide on loop invariant first: lo < hi (exclusive) or lo <= hi (inclusive), and match the update accordingly
- For “binary search on answer”: define the feasibility function before writing any binary search code
- The feasibility function must be monotonic: once it returns True, it stays True (or vice versa)
- Time is always O(log(search_space) × cost_of_feasibility_check)
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you search in a rotated sorted array?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “At any mid point, at least one half of the array is sorted. Check if the left half is sorted (nums[lo] <= nums[mid]). If yes, determine if the target is in the left half (nums[lo] <= target < nums[mid]); if so, search left, else search right. If the right half is sorted, apply the mirror logic. This handles all rotation cases in O(log n) without finding the rotation point first.” }
},
{
“@type”: “Question”,
“name”: “What is "binary search on the answer" and when do you apply it?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Binary search on the answer applies when: (1) the answer lies in a bounded range [lo, hi], and (2) there exists a monotonic feasibility function—once an answer value is feasible, all larger (or smaller) values are also feasible. Examples: minimum speed to eat bananas in H hours, minimum ship capacity to deliver in D days, minimum maximum subarray sum. Write the feasibility check first, then binary search over the answer range using your standard lo/hi template.” }
},
{
“@type”: “Question”,
“name”: “What is the difference between searching a fully sorted 2D matrix vs a row-and-column sorted matrix?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “A fully sorted matrix (each row sorted, last element of row i < first element of row i+1) can be treated as a flattened 1D sorted array—use standard binary search with index mapping: value = matrix[mid // cols][mid % cols]. A row-and-column sorted matrix (each row sorted left-to-right, each column sorted top-to-bottom, but rows not globally ordered) uses the staircase search: start at top-right, eliminate a row or column per step in O(m+n).” }
}
]
}