DSA: Binary Search on Monotonic Functions

7 min read6k
#DSA#BinarySearch

Solution to Last Week's Challenge

Last week's problem was: DSA: Prefix XOR Pattern

The optimal solution uses dsa: prefix xor pattern pattern with careful state management.

Complexity Analysis:

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Binary search is often introduced to computer science students as a way to find a target value in a sorted array. While this is an important use case, it represents only a fraction of the algorithm's true power. In senior-level software engineering and high-stakes technical interviews, we look at binary search through a different lens: the optimization of monotonic functions. This paradigm shift allows us to solve complex problems where the answer isn't sitting in an array, but rather exists within a theoretical range of possibilities.

In real-world systems, this pattern is ubiquitous. From database query optimizers determining the most efficient join order to load balancers finding the minimum threshold for rate-limiting, binary search on monotonic functions helps us find the "sweet spot" in a continuous or discrete range. If you can define a problem such that a "yes/no" answer follows a consistent trend—where once the answer becomes "yes," it stays "yes" for all larger values—you have a candidate for binary search.

Theory

The core concept of this pattern is the Predicate Function, often denoted as check(x). For a function to be searchable via binary search, it must be monotonic. This means that if check(x) is true, then for all y > x, check(y) must also be true (or vice-versa). We are essentially searching for the "boundary" or the "transition point" where the boolean result flips.

The search space is no longer indices of an array, but a range of possible answers [low, high]. The time complexity is defined as O(log(Range) * C), where Range is the distance between your lower and upper bounds, and C is the time complexity of your check function.

Pattern Visualization

When approaching these problems, the difficulty usually lies in defining the check function and identifying the range. The following flowchart illustrates the standard decision-making process for implementing this pattern.

Implementation

Let's look at a classic problem: Minimum Capacity to Ship Packages Within D Days. We have an array of weights and a maximum number of days. We need to find the minimum ship capacity that allows us to deliver all packages.

Brute Force Approach

The brute force way is to try every capacity starting from the maximum weight in the array up to the sum of all weights.

python
def shipWithinDays_Brute(weights, days):
    # Time Complexity: O(N * (Sum - Max)) - Too slow for large inputs
    # Space Complexity: O(1)
    low = max(weights)
    high = sum(weights)
    
    for capacity in range(low, high + 1):
        current_days = 1
        current_load = 0
        for w in weights:
            if current_load + w > capacity:
                current_days += 1
                current_load = 0
            current_load += w
        
        if current_days <= days:
            return capacity

Optimized Approach (Binary Search)

By recognizing that if we can ship with capacity X, we can definitely ship with capacity X+1, we identify the monotonicity.

python
def shipWithinDays(weights, days):
    # Time Complexity: O(N * log(Sum - Max))
    # Space Complexity: O(1)
    def check(capacity):
        # The greedy check function
        d = 1
        total = 0
        for w in weights:
            if total + w > capacity:
                d += 1
                total = w
            else:
                total += w
        return d <= days

    low = max(weights)
    high = sum(weights)
    ans = high
    
    while low <= high:
        mid = low + (high - low) // 2
        if check(mid):
            ans = mid
            high = mid - 1 # Try to find a smaller capacity
        else:
            low = mid + 1 # Need more capacity
            
    return ans

Complexity Analysis Table

ApproachTime ComplexitySpace ComplexityUse Case
Linear ScanO(N * Range)O(1)Small ranges, teaching purposes
Binary SearchO(N * log(Range))O(1)Large ranges, competitive programming
Precomputed BSO(log(Range))O(N)Multiple queries on static data

Common Patterns

1. Minimize the Maximum (Minimax)

Often phrased as "Find the minimum value such that the maximum of something is minimized."

python
# General template for Minimax
while low <= high:
    mid = (low + high) // 2
    if can_complete_with_max_limit(mid):
        res = mid
        high = mid - 1
    else:
        low = mid + 1

2. Maximize the Minimum

Common in resource allocation problems (e.g., placing cows in stalls to maximize the minimum distance between them).

python
# General template for Maximize Minimum
while low <= high:
    mid = (low + high) // 2
    if can_place_with_min_dist(mid):
        res = mid
        low = mid + 1
    else:
        high = mid - 1

Practice Problems

The following chart maps common problems by their difficulty and frequency in FAANG interviews.

This Week's Interview Challenge: The Efficient Woodcutter

Problem Statement: You are a lumberjack needing to cut M meters of wood. You have a set of trees with various heights. You can set your sawblade at a height H. Every portion of a tree that is taller than H is cut off. You need to find the maximum integer height H that allows you to collect at least M meters of wood.

Example 1:

  • Input: trees = [20, 15, 10, 17], M = 7
  • Output: 15
  • Explanation: At height 15, you cut 5m from the 20m tree and 2m from the 17m tree. Total = 7m.

Example 2:

  • Input: trees = [4, 42, 40, 26, 46], M = 20
  • Output: 36

Constraints:

  • 1 <= trees.length <= 10^5
  • 1 <= M <= 10^9
  • 1 <= trees[i] <= 10^9

Hints:

  1. If you lower the sawblade, do you get more or less wood?
  2. What is the smallest possible height for the blade? What is the largest?
  3. The amount of wood collected is a monotonic function of the blade height.
  4. Use a 64-bit integer for the wood sum to avoid overflow in some languages.

Template Code:

python
def max_saw_height(trees, m):
    def get_wood(h):
        # Calculate total wood collected at height h
        pass

    low = 0
    high = max(trees)
    result = 0
    
    # Your Binary Search Logic here
    return result

Submit your solution and check back next week for the detailed answer!

Conclusion

Mastering binary search on monotonic functions is a turning point for any software engineer. It transforms the way you look at optimization problems. Instead of trying to derive a direct mathematical formula for a result, you learn to build a "verifier" and let the logarithmic nature of binary search do the heavy lifting. When you see keywords like "minimum possible maximum" or "largest value such that," your mind should immediately pivot to this pattern.

  1. Identify the search space [min_possible, max_possible].
  2. Verify the monotonicity of the problem.
  3. Implement a greedy check(x) function.
  4. Handle your boundary conditions (low/high updates) carefully.

References