Binary Search Beyond Sorted Arrays: How to Use It on Rotated Arrays and Answer Spaces

Why binary search matters in interviews

Binary search is one of those patterns that looks simple on the surface and keeps showing up in harder forms during interviews. Everyone remembers the classic version: search a sorted array in O(log n). What trips people up is that interviewers rarely stop there. They rotate the array, hide the target in a transformed search space, or ask for the minimum feasible answer instead of an index.

If you only think of binary search as “search in a sorted list,” you miss a much bigger idea: binary search is really a way to exploit monotonic structure. Once you learn to recognize that structure, you can apply the pattern to rotated arrays, capacity planning, scheduling, optimization problems, and more.

That is why this pattern matters. It tests whether you understand the invariant behind the code, not just the syntax.

Problem statement

The binary search pattern appears in several interview variants:

1. Classic binary search: find a target in a sorted array.
2. Search rotated array: find a target in an array sorted then rotated.
3. Binary search on answer: find the smallest or largest value that satisfies a condition.

The main challenge is deciding:

• what range you are searching over,
• what condition is monotonic,
• and how to update boundaries safely.

If you can answer those three questions, you can solve most binary search variants.

Intuition: binary search is about monotonicity

In the standard version, the array is sorted, so values increase from left to right. That gives you a monotonic relationship:

• if nums[mid] < target, the target cannot be on the left,
• if nums[mid] > target, the target cannot be on the right.

For harder problems, the sorted structure may be hidden.

Rotated arrays

A rotated sorted array looks like this:

[4, 5, 6, 7, 0, 1, 2]

It is not globally sorted, but each half around the pivot is sorted. At every step, one side of mid is still ordered, and you can use that information to discard half the search space.

Binary search on answer

Sometimes the question is not “where is the value?” but “what is the smallest value that works?”

Example: “What is the minimum ship capacity needed to deliver all packages in 5 days?”

If a capacity C works, then any larger capacity also works. That creates a monotonic yes/no function:

• can_ship(C) = False for small capacities,
• then eventually can_ship(C) = True,
• and it stays true afterward.

That is exactly what binary search needs.

Approach 1: classic binary search

Let’s start with the base pattern, because the later variants build on it.

Idea

You keep two pointers, left and right, and repeatedly check the middle.

• If nums[mid] == target, return mid.
• If nums[mid] < target, search the right half.
• Otherwise, search the left half.

Python code

def binary_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

Worked example

Suppose nums = [1, 3, 5, 7, 9, 11] and target = 7.

This is the standard loop invariant: the target, if it exists, is always inside [left, right].

Approach 2: search in rotated sorted array

Now let’s handle the common interview twist.

Problem

Given a rotated sorted array and a target, return its index or -1 if it does not exist.

Example:

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0

Insight

Even though the whole array is not sorted, one side of mid is always sorted.

At each step:

• Determine whether the left half is sorted or the right half is sorted.
• Check whether the target falls inside the sorted half.
• If yes, discard the other half.
• If not, search the other side.

Python code

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

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Worked example

Search for 0 in [4, 5, 6, 7, 0, 1, 2].

Why this works

The key is that rotation preserves sorted order within one half of the array. You do not need the entire array to be sorted; you only need enough structure to eliminate half the search space each round.

Common pitfall

Do not try to compare nums[mid] directly to the target and guess direction the same way you would in a normal binary search. That fails because the rotation breaks global ordering.

Approach 3: binary search on answer

This is the form many candidates find hardest at first, but it is one of the most useful patterns in interviews.

Problem

Find the minimum ship capacity to deliver packages within days days.

Suppose weights = [1,2,3,4,5,6,7,8,9,10] and days = 5.

If capacity is too small, delivery takes too many days. If capacity is large enough, delivery fits within the limit. The feasibility changes monotonically.

Intuition

Instead of searching for an index, you search over the answer space.

• Lower bound: max package weight, because capacity must at least carry the heaviest package.
• Upper bound: sum of all weights, because one huge capacity can ship everything in one day.

For a candidate capacity mid, ask:

• Can I ship all packages within days using this capacity?

If yes, try smaller capacities. If no, try larger capacities.

Python code

def ship_within_days(weights, days, capacity):
    required_days = 1
    current_load = 0

    for weight in weights:
        if current_load + weight > capacity:
            required_days += 1
            current_load = 0
        current_load += weight

    return required_days <= days


def min_ship_capacity(weights, days):
    left, right = max(weights), sum(weights)
    answer = right

    while left <= right:
        mid = left + (right - left) // 2

        if ship_within_days(weights, days, mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer

Worked example

For weights = [3,2,2,4,1,4] and days = 3:

• left = 4, right = 16
• Try mid = 10: feasible, shrink right
• Try mid = 6: feasible, shrink right
• Try mid = 4: not feasible
• Try mid = 5: feasible

The minimum answer is 6.

Why this works

The feasibility check is monotonic:

• if capacity C works, then C+1, C+2, ... also work.
• if capacity C does not work, then smaller capacities will not work either.

That monotonicity turns the answer space into a sorted-like domain.

Another worked example: minimum feasible speed

Binary search on answer appears in many optimization problems. A classic one is “Koko Eating Bananas.”

Problem

Given piles of bananas and h hours, find the minimum eating speed so that Koko finishes on time.

Feasibility check

If Koko eats at speed k, then the time for one pile is ceil(pile / k).

If total time is within h, the speed works.

Python code

import math


def can_finish(piles, h, speed):
    hours = 0
    for pile in piles:
        hours += math.ceil(pile / speed)
    return hours <= h


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

    while left <= right:
        mid = left + (right - left) // 2

        if can_finish(piles, h, mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer

Example

For piles = [3, 6, 7, 11] and h = 8, the answer is 4.

This happens because speed 3 needs too many hours, while speed 4 is the smallest speed that fits.

Complexity analysis

Different binary search variants have different inner checks, but the outer structure is similar.

How to think about O(n log R)

If your answer space ranges from low to high, binary search takes log(high - low) iterations. If each iteration runs a linear feasibility check, the total becomes O(n log R).

This is still very efficient for large inputs.

How to recognize the pattern in interviews

Ask yourself these questions:

• Is the input sorted, or can I exploit partial ordering?
• Can I divide the space into two halves based on a condition?
• Does the condition stay true or false once it changes?
• Am I searching for an exact index, or the best valid answer?

If the answer is “the condition is monotonic,” binary search is probably a candidate.

Related problems

Here are some common variations that use the same core idea:

• Find First and Last Position of Element in Sorted Array
• Search in Rotated Sorted Array II
• Find Minimum in Rotated Sorted Array
• Koko Eating Bananas
• Capacity To Ship Packages Within D Days
• Split Array Largest Sum
• Median of Two Sorted Arrays
• Minimum Time to Complete Trips

Key takeaways

• Binary search is about monotonic structure, not just sorted arrays.
• In rotated arrays, one half is always sorted, which still lets you discard half the search space.
• In answer-space problems, you search over possible values and use a feasibility check.
• The hardest part is choosing the right invariant and boundary updates.
• When in doubt, write down what becomes impossible when mid changes.

Practice these next

1. Search in Rotated Sorted Array
2. Find Minimum in Rotated Sorted Array
3. Koko Eating Bananas
4. Capacity To Ship Packages Within D Days
5. Split Array Largest Sum

If you’d like to see the variables update live as you step through, check out codebrew.ai.