[Advanced] — A university-level introduction to the modified binary search pattern: what it is, why it exists, how it works, and how to implement it independently.

Before you start

  • You should understand binary search. See binary search if needed.
  • You should understand arrays and basic loops. See arrays if needed.

What you will be able to do after this lesson:

  1. Define the modified binary search pattern and explain why it adapts binary search to non-sorted data.
  2. Implement binary search on rotated sorted arrays.
  3. Apply the pattern to binary search on the answer (e.g., Koko eating bananas, minimum ship capacity).
  4. Explain the key insight that makes modified binary search work.

Study route: read the motivation and mechanism first, trace the worked example by hand, then attempt the independent task before looking at the hints.


1. Why this pattern exists (real-world motivation)

Imagine you’re searching for a target value in a sorted array, but the array has been rotated at some unknown pivot point. The array [4, 5, 6, 7, 0, 1, 2] is sorted, but rotated at index 4. Standard binary search won’t work because the array isn’t fully sorted.

However, even when the whole array isn’t sorted, at least one of the two halves around any mid is guaranteed to be sorted. This insight lets us adapt binary search: we can check which half is sorted, then determine if the target could be in that sorted half’s range, and search there; otherwise, the target must be in the other (still-rotated) half.

This is the modified binary search pattern: adapt the halving logic of binary search to arrays that aren’t fully sorted in the plain sense — most commonly, a sorted array that’s been rotated at some unknown pivot. The core trick: even when the whole array isn’t sorted, at least one of the two halves around any mid always is, and you can use that fact to decide which half to search.

There’s another variant worth knowing separately: binary search on the answer — instead of binary searching over an array, you binary search over the space of possible answers. This applies when a problem asks for the optimal value satisfying some condition, and “is candidate value X good enough?” is cheap to check and has a monotonic answer (every value below some threshold fails, every value at or above it works, with no flip-flopping).


2. Definitions and terminology

TermPlain-English definitionExample / analogy
Modified binary searchAdapt binary search to arrays that aren’t fully sorted but have some structureSearch in a rotated sorted array
Rotated sorted arrayA sorted array that’s been rotated at some unknown pivot point[4, 5, 6, 7, 0, 1, 2] (sorted [0, 1, 2, 4, 5, 6, 7] rotated at index 4)
Binary search on the answerBinary search over the space of possible answers, not array indicesFind minimum eating speed for Koko to finish bananas in H hours
Monotonic predicateA condition that, once true, stays true for all larger values”Can Koko eat at speed X in H hours?” (true for X >= some threshold)

3. How it works — step by step

Binary search on rotated sorted array

At each step, first figure out which half is the “normal” sorted one (compare nums[left] to nums[mid]), then check whether the target could be in that sorted half’s range — if so, search there; otherwise, the target must be in the other (still-rotated) half.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:            # left half is normally sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:                                   # right half is normally sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

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

left=0 right=6 mid=3  nums[3]=7
  nums[0]=4 <= 7 -> left half [4,5,6,7] is sorted
  is 0 in [4, 7)? no -> search right half: left=4
left=4 right=6 mid=5  nums[5]=1
  nums[4]=0 <= 1 -> left half [0,1] is sorted
  is 0 in [0, 1)? yes -> search left half: right=4
left=4 right=4 mid=4  nums[4]=0 == target -> found at index 4

Binary search on the answer

The rotated-array case above still binary-searches over the array. A distinct and very commonly tested variant instead binary-searches over the space of possible answers:

Example: given n holes in a roof and k boards, find the minimum board size that lets all holes be covered using at most k boards.

def min_board_size(holes, k):
    def boards_needed(size):          # greedy check: how many boards of this size are needed?
        count, last_covered = 0, -1
        for i, has_hole in enumerate(holes):
            if has_hole and last_covered < i:
                count += 1
                last_covered = i + size - 1
        return count
 
    lo, hi, result = 1, len(holes), -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if boards_needed(mid) <= k:     # mid is "good enough" — try to do better
            result = mid
            hi = mid - 1
        else:                            # mid isn't enough — need a bigger size
            lo = mid + 1
    return result

The shape to recognize: lo/hi bound a range of candidate answers, not array indices; the “check” function (boards_needed here) is usually its own separate O(n) pass; and the overall complexity becomes O(n log n) — an O(n) check repeated O(log n) times — rather than the plain O(log n) of searching an already-built array.

Other classic problems in this exact shape: “minimum ship capacity to deliver packages within D days,” “Koko eating bananas” (minimum eating speed to finish within h hours), “split array into k parts minimizing the largest part’s sum.”

The tell that a problem wants this pattern: it asks for a minimum/maximum value satisfying a constraint, and you can imagine a “does value X work?” check that’s monotonic (works for X implies works for every value past X in the same direction) — that monotonicity is precisely what makes binary search valid here, same as sortedness is what makes it valid on an array.


4. Implementation — complete runnable example

Runnable example: save as modified_binary_search_lab.py and run python3 modified_binary_search_lab.py. It uses only Python’s standard library and creates no external files.

from typing import List
 
 
def search_rotated(nums: List[int], target: int) -> int:
    """Search in a rotated sorted array."""
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:            # left half is normally sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:                                   # right half is normally sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1
 
 
def min_eating_speed(piles: List[int], h: int) -> int:
    """Find minimum eating speed for Koko to finish all piles in h hours."""
    def can_finish(speed: int) -> bool:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # ceiling division
            if hours > h:
                return False
        return True
 
    lo, hi = 1, max(piles)
    result = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_finish(mid):      # mid is "good enough" — try to do better
            result = mid
            hi = mid - 1
        else:                    # mid isn't enough — need a bigger speed
            lo = mid + 1
    return result
 
 
def min_ship_capacity(weights: List[int], days: int) -> int:
    """Find minimum ship capacity to ship all weights in given days."""
    def can_ship(capacity: int) -> bool:
        days_needed, current_load = 1, 0
        for weight in weights:
            if weight > capacity:        # a single package cannot be split
                return False
            if current_load + weight > capacity:
                days_needed += 1         # start a new day
                current_load = 0
            current_load += weight
        return days_needed <= days
 
    lo, hi = max(weights), sum(weights)
    result = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_ship(mid):       # mid is "good enough" — try to do better
            result = mid
            hi = mid - 1
        else:                   # mid isn't enough — need a bigger capacity
            lo = mid + 1
    return result
 
 
if __name__ == "__main__":
    # Test case 1: search in rotated sorted array
    nums1 = [4, 5, 6, 7, 0, 1, 2]
    target1 = 0
    result1 = search_rotated(nums1, target1)
    print(f"Test 1 - search in rotated sorted array:")
    print(f"nums={nums1}, target={target1} -> index {result1}")
    assert result1 == 4, f"Expected 4, got {result1}"
 
    # Test case 2: Koko eating bananas
    piles2 = [3, 6, 7, 11]
    h2 = 8
    result2 = min_eating_speed(piles2, h2)
    print(f"\nTest 2 - Koko eating bananas:")
    print(f"piles={piles2}, h={h2} -> speed {result2}")
    assert result2 == 4, f"Expected 4, got {result2}"
 
    # Test case 3: ship capacity
    weights3 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    days3 = 5
    result3 = min_ship_capacity(weights3, days3)
    print(f"\nTest 3 - ship capacity:")
    print(f"weights={weights3}, days={days3} -> capacity {result3}")
 
    print("\nmodified_binary_search_lab: passed")

Expected output:

Test 1 - search in rotated sorted array:
nums=[4, 5, 6, 7, 0, 1, 2], target=0 -> index 4

Test 2 - Koko eating bananas:
piles=[3, 6, 7, 11], h=8 -> speed 4

Test 3 - ship capacity:
weights=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days=5 -> capacity 15

modified_binary_search_lab: passed

Search a 2D Matrix

Treat the 2D matrix as one flat sorted array:

def search_2d_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
 
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
 
    while left <= right:
        mid = (left + right) // 2
        row, col = divmod(mid, n)
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return False

Median of Two Sorted Arrays

Binary search on the partition point:

def find_median_sorted_arrays(nums1, nums2):
    # Ensure nums1 is the smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
 
    m, n = len(nums1), len(nums2)
    lo, hi = 0, m
 
    while lo <= hi:
        partition1 = (lo + hi) // 2
        partition2 = (m + n + 1) // 2 - partition1
 
        max_left1 = float('-inf') if partition1 == 0 else nums1[partition1 - 1]
        min_right1 = float('inf') if partition1 == m else nums1[partition1]
        max_left2 = float('-inf') if partition2 == 0 else nums2[partition2 - 1]
        min_right2 = float('inf') if partition2 == n else nums2[partition2]
 
        if max_left1 <= min_right2 and max_left2 <= min_right1:
            # Found the correct partition
            if (m + n) % 2 == 0:
                return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2
            else:
                return max(max_left1, max_left2)
        elif max_left1 > min_right2:
            hi = partition1 - 1
        else:
            lo = partition1 + 1
 
    return 0

6. Complexity

  • Rotated array search: O(log n) — same as standard binary search; the extra “which half is sorted” check is O(1) work added to each step.
  • Binary search on the answer: O(n log n) — an O(n) check repeated O(log n) times (where n is the size of the input to the check function).

7. Tradeoffs and limitations

  • Rotated array search: Requires the array to be sorted and rotated (not arbitrary unsorted data). The algorithm assumes exactly one rotation point.
  • Binary search on the answer: Requires the predicate to be monotonic (once true, stays true for larger values). Not all optimization problems have this property.
  • Rotated array search: The “which half is sorted” check can be confusing; understanding why it works is key.

8. Check your understanding (self-assessment)

Attempt these without the note, then compare your reasoning below.

  1. Question: Given nums = [4, 5, 6, 7, 0, 1, 2] and target = 0, trace through the rotated array search algorithm step by step.
  2. Question: Why does the “which half is sorted” check work for rotated arrays?
  3. Question: What makes a problem suitable for binary search on the answer?

Answers — after your attempt

  1. left=0 right=6 mid=3 nums[3]=7
    nums[0]=4 <= 7 -> left half [4,5,6,7] is sorted
    is 0 in [4, 7)? no -> search right half: left=4
    left=4 right=6 mid=5 nums[5]=1
    nums[4]=0 <= 1 -> left half [0,1] is sorted
    is 0 in [0, 1)? yes -> search left half: right=4
    left=4 right=4 mid=4 nums[4]=0 == target -> found at index 4
  2. Even when the whole array isn’t sorted, at least one of the two halves around any mid is guaranteed to be sorted. This is because the array was originally sorted and then rotated at some point. The sorted half’s range is contiguous, so we can check if the target could be in that range.
  3. A problem is suitable for binary search on the answer if:
    • It asks for a minimum/maximum value satisfying some constraint.
    • You can imagine a “does value X work?” check that’s monotonic (once true, stays true for larger values).
    • The check function is relatively efficient (usually O(n) or better).

9. Practice — independent task

Task: Implement a function min_eating_speed(piles, h) that returns the minimum eating speed for Koko to finish all piles in h hours. Use the binary search on the answer pattern. Test it with the following cases:

  • piles = [3, 6, 7, 11], h = 8 → expected 4
  • piles = [30, 11, 23, 4, 20], h = 5 → expected 30

Done when: your function returns the correct minimum eating speed for both test cases.


Practice problems

In the NeetCode 150 — solved and written up here:

  1. Binary Search (LeetCode #704) — the baseline — settle your loop invariant here, once.
  2. Search a 2D Matrix (LeetCode #74) — index arithmetic turns the grid into one sorted array.
  3. Koko Eating Bananas (LeetCode #875) — binary search on the answer, with a feasibility predicate.
  4. Find Minimum in Rotated Sorted Array (LeetCode #153) — compare mid against the right end, not the left.
  5. Search in Rotated Sorted Array (LeetCode #33) — identify which half is sorted, then decide.
  6. Time Based Key-Value Store (LeetCode #981) — search for the largest timestamp not exceeding the query.
  7. Median of Two Sorted Arrays (LeetCode #4) — binary search on the partition point; the hardest in the set.

Not in the NeetCode 150 — worth doing on LeetCode directly, since they drill boundary-finding and search-on-the-answer separately:

  1. Capacity To Ship Packages Within D Days (#1011) — the problem the lab’s min_ship_capacity solves — do it after reading section 3.
  2. First Bad Version (#278) — the minimal find-the-boundary template.
  3. Search Insert Position (#35) — where the two loop conventions visibly differ.
  4. Find First and Last Position of Element in Sorted Array (#34) — two boundary searches in one problem.
  5. Find Peak Element (#162) — binary search with no sorted order at all, only a local condition.
  6. Split Array Largest Sum (#410) — search-on-the-answer again, with a harder predicate.

Before moving on

You are done with this pattern when you can, closed-book:

  • Write a binary search with correct bounds and no infinite loop.
  • Explain how to decide which half of a rotated array is sorted.
  • Implement search-in-rotated-array independently.
  • Explain why low + (high - low) // 2 is preferred over (low + high) // 2.

Recap: Binary search halves the search space each step by exploiting an ordering invariant. The variants keep that invariant while the data is transformed — in a rotated array, at least one half is always properly sorted, so you test which and recurse into the half that could contain the target. The bugs are almost always in the boundary conditions rather than the idea.

Next: binary-tree-traversal-pattern — the same divide-and-conquer instinct applied to a branching structure instead of a linear one.


11. Further reading

The pattern appears in many contexts beyond LeetCode:

  • Optimization problems: Finding optimal parameters in engineering design
  • Resource allocation: Determining optimal allocation of limited resources
  • Production planning: Finding optimal production rates
  • Network routing: Finding optimal path costs

The core idea — using binary search over a space of possible answers when you have a monotonic predicate — is a fundamental algorithmic technique that appears whenever you need to find an optimal value efficiently.

↑ Back to LeetCode Patterns — University-Style Teaching Notes