Module 4.1 ⏱ 35 min read ⚡ Searching & Optimization

Advanced Binary Search

Master binary search boundaries, locate duplicate occurrences, and transform complex optimization challenges into monotonic search space problems.

1. Binary Search on Sorted Arrays & Boundary Conditions

Standard binary search looks for a precise target in an ordered array in $O(\log n)$ time. However, real-world problems often feature duplicates or require finding structural boundaries (such as lower and upper bounds). Handling conditions like `left <= right`, `mid = left + (right - left) / 2`, and deciding whether to move `left = mid + 1` or `right = mid - 1` are critical to avoid infinite loops and fencepost errors.

Finding First and Last Positions: By modifying how pointers behave when `nums[mid] == target`, you can perform two separate binary searches: one to locate the leftmost boundary and another for the rightmost boundary.

2. Binary Search on Answer Spaces (Monotonic Search Spaces)

When an optimization problem asks for the minimum or maximum valid value within a known numerical range, and feasibility follows a monotonic pattern (i.e., if value $X$ works, either all values greater than $X$ work or all values smaller than $X$ work), you can apply binary search directly onto the answer space rather than the input array.

// C++ Solution: Split Array Largest Sum (Binary Search on Answer Space)
#include <vector>
#include <numeric>
#include <algorithm>

class Solution {
public:
    int splitArray(std::vector<int>& nums, int k) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = std::max(left, num);
            right += num;
        }
        int ans = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isValid(nums, k, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
private:
    bool isValid(const std::vector<int>& nums, int k, int max_sum) {
        int count = 1, current_sum = 0;
        for (int num : nums) {
            if (current_sum + num > max_sum) {
                count++;
                current_sum = num;
            } else {
                current_sum += num;
            }
        }
        return count <= k;
    }
};
            

# Python Solution: Split Array Largest Sum (Binary Search on Answer Space)
class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        left, right = max(nums), sum(nums)
        ans = right
        
        def is_valid(max_sum):
            count, current_sum = 1, 0
            for num in nums:
                if current_sum + num > max_sum:
                    count += 1
                    current_sum = num
                else:
                    current_sum += num
            return count <= k
        
        while left <= right:
            mid = (left + right) // 2
            if is_valid(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans
            

// Java Solution: Split Array Largest Sum (Binary Search on Answer Space)
class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0, right = 0;
        for (int num : nums) {
            left = Math.max(left, num);
            right += num;
        }
        int ans = right;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (isValid(nums, k, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
    
    private boolean isValid(int[] nums, int k, int maxSum) {
        int count = 1, currentSum = 0;
        for (int num : nums) {
            if (currentSum + num > maxSum) {
                count++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        return count <= k;
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for finding the First and Last Position of an Element and solving the Split Array Largest Sum problem.

Quick Check: Test Your Intuition

What core property must an answer space possess for binary search to be successfully applied to an optimization problem?