Binary Search Interview Questions: Beyond Sorted Arrays

Binary search isn't just for sorted arrays. The real power of binary search is searching a monotonic function's answer space. If you can define a condition that's false for some values and true for others, and that condition transitions at most once from false to true, binary search finds the transition point in O(log n). This pattern unlocks dozens of problems that don't look like binary search at first glance.

When to Use Binary Search

Binary search is the right approach when:

• The input is sorted (classic use case)
• You're searching for a boundary in a monotonic condition (e.g., "minimum capacity such that...")
• You can formulate a yes/no decision problem where the answer space is monotonic
• The problem asks for the minimum or maximum value that satisfies a constraint
• You see keywords like "minimize the maximum," "maximize the minimum," or "find the smallest X such that..."

The trigger: Can you check if a candidate answer works in O(n) or O(n log n)? If yes and the answer space is monotonic, binary search applies.

Pattern 1: Index Binary Search (Classic)

Search for a target value in a sorted array by comparing the middle element. This is the textbook binary search.

Example: Search in Sorted Array

def search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Time: O(log n). Space: O(1).

Example: Search in Rotated Sorted Array

A rotated sorted array is sorted but rotated at some pivot. The key insight: at least one half is always sorted. Check which half is sorted, then decide which half to search.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Walkthrough with [4,5,6,7,0,1,2], target = 0:

1. left=0, right=6, mid=3 → nums[3]=7, left half [4,5,6,7] sorted
2. 4 ≤ 0 < 7? No → search right half
3. left=4, right=6, mid=5 → nums[5]=1, right half [1,2] sorted
4. 1 < 0 ≤ 2? No → search left half
5. left=4, right=4, mid=4 → nums[4]=0 → found

Time: O(log n). Space: O(1).

Pattern 2: Answer Space Binary Search

Instead of searching an array, you search over a range of possible answers. Define a predicate function can_satisfy(x) that returns True if answer x works. Binary search finds the minimum x where the predicate becomes True.

Example: Find Minimum in Rotated Sorted Array

Find the minimum element in a rotated sorted array with no duplicates. The minimum is the only element smaller than its predecessor.

def find_min(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[left]

Walkthrough with [4,5,6,7,0,1,2]:

1. left=0, right=6, mid=3 → nums[3]=7 > nums[6]=2 → left=4
2. left=4, right=6, mid=5 → nums[5]=1 ≤ nums[6]=2 → right=5
3. left=4, right=5, mid=4 → nums[4]=0 ≤ nums[5]=1 → right=4
4. left=4, right=4 → nums[4]=0

Time: O(log n). Space: O(1).

Example: Koko Eating Bananas

Koko loves bananas. She eats at a constant rate and has h hours to eat all piles. Find the minimum integer k such that she can finish all piles in h hours at rate k.

import math

def min_eating_speed(piles, h):
    left, right = 1, max(piles)

    while left < right:
        mid = left + (right - left) // 2
        hours = sum(math.ceil(p / mid) for p in piles)
        if hours <= h:
            right = mid
        else:
            left = mid + 1

    return left

The answer space is [1, max(piles)]. The predicate: "can Koko finish all piles in h hours at rate mid?" If yes, try a smaller rate. If no, increase the rate.

Time: O(n × log(max(piles))). Space: O(1).

Pattern 3: Binary Search on Result

Some problems ask you to find the maximum or minimum value that satisfies a constraint. You binary search on the answer and check feasibility with a helper function.

Example: Capacity to Ship Packages Within D Days

Given package weights and D days, find the minimum capacity of a ship that can ship all packages within D days. Packages must be shipped in order.

def ship_within_days(weights, days):
    def can_ship(capacity):
        current_load = 0
        days_needed = 1
        for w in weights:
            if current_load + w > capacity:
                days_needed += 1
                current_load = 0
            current_load += w
        return days_needed <= days

    left = max(weights)
    right = sum(weights)

    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1

    return left

Walkthrough with weights = [1,2,3,4,5,6,7,8,9,10], days = 5:

Answer space: [10, 55] (max weight to total weight)

1. mid=32 → can ship in 5 days? Yes → right=32
2. mid=21 → can ship in 5 days? Yes → right=21
3. mid=15 → can ship in 5 days? Yes → right=15
4. mid=12 → can ship in 5 days? Yes → right=12
5. mid=11 → can ship in 5 days? No → left=12
6. Result: 12

Time: O(n × log(sum(weights))). Space: O(1).

Example: Split Array Largest Sum

Split an array into m non-empty subarrays such that the largest sum among these subarrays is minimized. This is the same pattern as ship packages.

def split_array(nums, m):
    def can_split(max_sum):
        count = 1
        current = 0
        for num in nums:
            if current + num > max_sum:
                count += 1
                current = 0
            current += num
        return count <= m

    left = max(nums)
    right = sum(nums)

    while left < right:
        mid = left + (right - left) // 2
        if can_split(mid):
            right = mid
        else:
            left = mid + 1

    return left

Time: O(n × log(sum(nums))). Space: O(1).

Complexity Summary

Where R = range of possible answers (typically max - min or sum).

Common Mistakes

1. Using left + right for mid instead of left + (right - left) // 2. The former can overflow for very large indices. In Python this doesn't matter (arbitrary precision integers), but it's a bad habit and matters in other languages.

2. Infinite loops with left < right. If left never changes in the else branch, the loop runs forever. Always ensure left moves toward right (or vice versa).

3. Off-by-one in the answer space. For "minimum value that satisfies," use left < right with right = mid. For "maximum value that satisfies," use left < right with left = mid + 1. Mixing these up causes off-by-one errors.

4. Binary searching on a non-monotonic condition. The predicate must transition from False to True at most once. If it oscillates (True, False, True), binary search gives wrong results. Verify monotonicity before applying binary search.

5. Using <= vs < in the while condition. left <= right searches the full range including both endpoints. left < right converges to a single point. Choose based on whether you need to check the boundary.

Practice Problems

These problems cover the three binary search patterns. Solve them in order.

1. Search in Rotated Sorted Array — Index binary search on a rotated array. Find which half is sorted, then decide.

2. Find Minimum in Rotated Sorted Array — Binary search for the rotation point. The minimum is where nums[mid] > nums[right].

3. Capacity to Ship Packages Within D Days — Answer space binary search. Binary search on capacity, check feasibility in O(n).

4. Koko Eating Bananas — Answer space binary search. Find minimum eating speed to finish all piles within h hours.

5. Split Array Largest Sum — Answer space binary search. Minimize the largest subarray sum across m splits.

Practice These Patterns With Alex

Binary search problems require identifying the answer space and proving monotonicity — skills that are hard to build through LeetCode alone. Practice with an AI interviewer who asks you to justify your binary search bounds and explain why the condition is monotonic.

Start a mock coding interview →

Frequently Asked Questions