How do you search in a rotated sorted array?

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.

What is "binary search on the answer" and when do you apply it?

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.

What is the difference between searching a fully sorted 2D matrix vs a row-and-column sorted matrix?

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).

Advanced Binary Search Interview Patterns: Rotated Array, Search on Answer

Q: What is "binary search on the answer" and when do you apply it?

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.

Q: What is the difference between searching a fully sorted 2D matrix vs a row-and-column sorted matrix?

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).

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) // 2 to 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)

Shopify Interview Guide

Uber Interview Guide

Databricks Interview Guide

LinkedIn Interview Guide

Apple Interview Guide

Meta Interview Guide