Skip to main content

Advanced Binary Search

TL;DR​

Advanced binary search extends beyond sorted arrays by identifying monotonic properties in problems. Search rotated arrays by finding pivot points. Find peak elements using monotonic sequences. Solve optimization problems (minimize maximum, capacity limits) by binary searching over answer ranges. Key insight: if you can verify a candidate answer in O(n), binary search can find the optimal answer in O(n log n) or better. Time complexity remains O(log n) comparisons regardless of problem complexity.

Core Concepts​

Monotonic Property Recognition​

The foundation of advanced binary search is identifying monotonic properties—relationships where adding more of something creates a consistent directional change in outcome.

Examples of monotonic properties:

  • Rotated array: All elements left of pivot are >= all elements right of pivot
  • Peak finding: Values increase then decrease (mountain shape)
  • Capacity problems: If capacity X works, all capacities > X work (monotonic in feasibility)
  • Resource allocation: More resources → better outcome (monotonic relationship)

How to identify: Ask "if X works, do all larger values work?" or "if X fails, do all smaller values fail?" If yes, you have monotonicity.

Search Space Abstraction​

Instead of searching through array indices, advanced binary search searches through answer spaces:

  • For "minimize the maximum load": search range [1, max_load]
  • For "find peak element": search indices with mountain property
  • For "split array": search possible split sizes

The invariant remains: at each step, eliminate half the search space by checking properties at the midpoint.

Finding Boundaries in Rotated Arrays​

A rotated sorted array maintains local ordering properties. The key is identifying which half is properly sorted:

Original: [1,2,3,4,5,6,7]
Rotated:  [4,5,6,7,1,2,3]

In the rotated array: left half [4,5,6,7] is sorted, right half [1,2,3] is sorted. The transition point (pivot) is where arr[i] > arr[i+1].

Key Algorithms​

Search in Rotated Sorted Array​

Problem: Find a target value in a rotated sorted array in O(log n) time.

Approach:

  1. Identify which half is properly sorted
  2. Determine if target is in sorted half
  3. Binary search on appropriate half

Key insight: One half is always sorted, allowing us to determine if target must be there.

Find Peak Element​

Problem: Find element greater than its neighbors in array where arr[-1] and arr[len] are -∞.

Approach:

  1. Compare mid with neighbors
  2. Peak must be in direction of larger neighbor
  3. Continue narrowing search space

Key insight: A larger neighbor always leads toward peak due to problem constraints.

Minimize Maximum (Capacity to Ship Packages)​

Problem: Given packages and days, find minimum capacity needed to ship all packages in given days, maintaining order.

Approach:

  1. Search range: [max_package_weight, sum_all_packages]
  2. For each candidate capacity, check if feasible
  3. Find minimum capacity that works

Key insight: Monotonicity: if capacity works, larger capacities work. Binary search over capacities, not indices.

Practical Example​

# Search in Rotated Sorted Array
def search_rotated(arr, target):
    left, right = 0, len(arr) - 1

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

        # Determine which half is sorted
        if arr[left] <= arr[mid]:  # Left half sorted
            if arr[left] <= target < arr[mid]:
                right = mid - 1  # Target in left half
            else:
                left = mid + 1   # Target in right half
        else:  # Right half sorted
            if arr[mid] < target <= arr[right]:
                left = mid + 1   # Target in right half
            else:
                right = mid - 1  # Target in left half

    return -1

# Find Peak Element
def find_peak(arr):
    left, right = 0, len(arr) - 1

    while left < right:
        mid = (left + right) // 2
        if arr[mid] > arr[mid + 1]:
            right = mid  # Peak in left half (including mid)
        else:
            left = mid + 1  # Peak in right half

    return left

# Capacity to Ship Packages in D Days
def ship_within_days(packages, days):
    def can_ship(capacity):
        current_load = 0
        days_used = 1
        for package in packages:
            if current_load + package > capacity:
                days_used += 1
                current_load = package
            else:
                current_load += package
        return days_used <= days

    left = max(packages)  # Min capacity: largest package
    right = sum(packages)  # Max capacity: all in one day

    while left < right:
        mid = (left + right) // 2
        if can_ship(mid):
            right = mid  # Try smaller capacity
        else:
            left = mid + 1  # Need larger capacity

    return left

# Minimize Maximum Load Across K Partitions
def minimize_max_load(weights, k):
    def can_partition(max_load):
        partitions = 1
        current_sum = 0
        for weight in weights:
            if current_sum + weight > max_load:
                partitions += 1
                current_sum = weight
            else:
                current_sum += weight
        return partitions <= k

    left = max(weights)  # Min possible max load
    right = sum(weights)  # Max possible max load

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

    return left

# Test
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # Output: 4
print(find_peak([1, 2, 3, 1]))  # Output: 2
print(ship_within_days([1, 2, 3, 4, 5, 4, 1, 1, 4, 10], 5))  # Output: 15
print(minimize_max_load([1, 2, 3, 4, 5], 3))  # Output: 5

Common Pitfalls​

warning

Incorrect half detection in rotated arrays: Must verify with left boundary (arr[left]), not just relative to mid. Failing to check arr[left] <= arr[mid] leads to wrong half elimination.

Not accounting for duplicate values: In rotated arrays with duplicates, arr[left] == arr[mid] == arr[right] prevents determining sorted half. Requires shrinking boundaries to unique values.

Off-by-one errors on range bounds: For optimization problems, lower bound should be maximum element (not 1 or 0), upper bound should be sum. Wrong initialization fails to capture valid range.

Assuming monotonicity without verification: Not every "search" problem has binary searchable answer space. Verify that if candidate works, all larger candidates work (or vice versa).

Missing boundary checks for peak finding: Peak element must be compared against valid neighbors (handle edges where arr[-1] and arr[len] are -∞). Index out of bounds crashes.

Self-Check​

  1. How do you determine which half of a rotated array is properly sorted? Why not just compare target with arr[mid]?
  2. Why does minimizing maximum load admit a binary search solution? What property must hold?
  3. Can binary search find a peak in O(log n) if we don't sort the array? Explain the monotonic property that makes this possible.

One Takeaway​

info

Advanced binary search discovers hidden monotonic properties in non-obvious problems. The key breakthrough is recognizing that feasibility conditions (can capacity X work?) create a searchable answer space. By binary searching feasibility ranges instead of array indices, you solve complex optimization problems in O(log n) comparisons plus verification cost, achieving dramatic speedups over brute-force enumeration.

References​

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  • LeetCode Problem 33: Search in Rotated Sorted Array
  • LeetCode Problem 162: Find Peak Element
  • LeetCode Problem 1011: Capacity to Ship Packages Within D Days