Binary Search Questions at Amazon: What to Expect

Binary Search isn't just about finding an element in a sorted array. At Amazon, it's a fundamental pattern for optimizing solutions to problems involving massive datasets, which is core to their scale. With 181 Binary Search questions in their question bank, it appears in nearly 1 in 10 Amazon problems. Interviewers use it to assess your ability to think beyond brute force and design efficient, scalable algorithms—a daily requirement for Amazon engineers.

What to Expect — Types of Problems

You will rarely see a textbook "find the index of a target" question. Instead, Amazon applies Binary Search in more advanced contexts. Expect these categories:

1. Search in a Modified or Conceptual Sorted Space: The array isn't obviously sorted, or the sorted property is conceptual. Examples include finding a peak element, searching in a rotated sorted array, or finding the minimum in a rotated array. These test your ability to identify the invariant that allows Binary Search.

2. Binary Search on Answer (or "Guess the Answer"): This is the most common and critical pattern. You use Binary Search to guess the optimal answer and verify it with a helper function. Classic Amazon problems include: "Koko Eating Bananas" (finding the minimum eating speed), "Capacity To Ship Packages Within D Days" (finding the minimum ship capacity), and "Split Array Largest Sum" (minimizing the largest subarray sum). These model real-world optimization problems like resource allocation.

3. Search in Structured Data: Applying Binary Search to matrices (row-wise and column-wise sorted), infinite streams, or unknown-sized arrays. Questions like "Search a 2D Matrix II" test your ability to reduce the search space in multiple dimensions.

How to Prepare — Study Tips with One Code Example

Master the pattern, not just the implementation. The core template is simple, but the challenge is knowing when and how to apply it.

• Tip 1: Recognize the "search space." If the problem asks for a minimum or maximum of something (speed, capacity, distance) and you can write a function canDo(guess) that checks feasibility, you likely need Binary Search on Answer.
• Tip 2: Always clearly define your left and right boundaries. left is often the minimum possible answer (e.g., 1 banana/hour), and right is the maximum (e.g., the largest pile of bananas).
• Tip 3: Decide your loop condition (left < right vs. left <= right) and how you update bounds (mid, mid - 1, mid + 1) consistently to avoid infinite loops. Stick with one template.

Here is the essential "Binary Search on Answer" pattern applied to "Koko Eating Bananas":

def minEatingSpeed(piles, h):
    def can_eat(k):
        hours = 0
        for p in piles:
            hours += (p + k - 1) // k  # ceil(p / k)
        return hours <= h

    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        if can_eat(mid):
            right = mid  # Try a smaller speed
        else:
            left = mid + 1  # Need a faster speed
    return left

Recommended Practice Order

Build your skills progressively:

1. Foundation: Standard Binary Search (704), First/Last Position in Sorted Array (34).
2. Modified Space: Find Minimum in Rotated Sorted Array (153), Search in Rotated Sorted Array (33), Peak Element (162).
3. Binary Search on Answer: Koko Eating Bananas (875), Capacity To Ship Packages (1011), Split Array Largest Sum (410).
4. 2D & Advanced: Search a 2D Matrix II (240), Find Minimum in Rotated Sorted Array II (154), Time Based Key-Value Store (981).

Practice Binary Search at Amazon