Mastering Binary Search: Tackling Problems with Upper and Lower Bounds

August 22, 2024

dsa binary search

Binary search is a powerful tool, especially when dealing with sorted data. Beyond just finding elements, binary search can be adapted to solve a variety of problems by leveraging upper bounds and lower bounds. In this post, I’ll share how understanding these bounds can help solve different kinds of scenarios, using the LeetCode problem “410: Split Array Largest Sum” as an example.

Understanding Upper and Lower Bounds

Before diving into problem-solving, let’s recap:

Binary Search: A search algorithm that finds the target in a sorted array by repeatedly dividing the search space in half. It compares the middle element with the target and eliminates half of the array based on the comparison.
Lower Bound: The smallest index in a sorted array where a value can be inserted without disrupting the order. If you’re looking for a target value, the lower bound is the first index where the array element is not less than the target.
Upper Bound: The smallest index in a sorted array where an element is strictly greater than the target value. This helps determine where a value can be placed to maintain the order if it must be placed strictly before any larger elements.

Applying These Concepts to “Split Array Largest Sum”

In the “410: Split Array Largest Sum” problem, the goal is to minimize the largest sum among “k” subarrays, where the array is split accordingly. This problem can be solved efficiently using binary search by applying the concept of finding an appropriate bound. Let’s understand this with a test case.

Given: nums = [7, 2, 5, 10, 8] and k = 2

Here, we can have a total of four possible pairs of subarrays:

Pair-1	Pair-2	Sum of Pairs	Larger Sum
[7]	[2,5,10,8]	[7,25]	25
[7,2]	[5,10,8]	[9,23]	23
[7,2,5]	[10,8]	[14,18]	18
[7,2,5,10]	[8]	[24,8]	24

Among the largest sums, the minimum largest sum is 18. Thus, 18 is our answer.

Final Result: The minimum possible maximum subarray sum is 18.

Key Idea:

The problem can be reduced to finding the minimum possible “largest sum” for which it’s feasible to split the array into k subarrays.

Steps:

Define Search Space:
- The smallest possible value for the largest sum (left) would be the maximum element in the array.
- The largest possible value (right) is the sum of all elements in the array (if the array is not split at all).

Brainstorm 🤔

You might wonder why we consider the sum of all elements as the upper bound, even though the array needs to be split into "k" subarrays. The reason is that directly calculating the maximum subarray sum for "k" splits and then using that as our upper bound would be inefficient. Instead, by simply using the sum of all elements as the upper limit, we streamline the process and avoid the need for additional code to determine the maximum subarray sum for a given "k". This approach is both simpler and more efficient.

Binary Search:

Perform binary search within this range [left, right].
For each midpoint (mid), determine if it’s possible to split the array such that the largest sum of the subarrays does not exceed mid.

Check Feasibility:
- To check if a particular mid value can work, iterate through the array, attempting to form subarrays without exceeding the mid value.
Update Bounds:
- If splitting is possible, it means you might be able to achieve a smaller “largest sum”, so adjust the right bound.
- If it’s not possible, you need a higher mid value, so adjust the left bound.

Java Implementation:

class Solution {
    public int splitArray(int[] nums, int k) {

        int l = Integer.MIN_VALUE;
        int h = 0;
        for(int num : nums){
            l = Math.max(l, num);
            h += num;
        }
        while(l < h){
            int mid = l + (h - l) / 2;
            if(count(mid, nums) > k){
                l = mid + 1;
            } else {
                h = mid;
            }
        }

        return l;
    }

    int count(int mid, int[] nums) {
        int count = 0;
        int sum = 0;
        for(int num : nums){
            if(sum + num > mid){
                count++;
                sum = num;
                if(count > k) return count + 1;
            } else {
                sum += num;
            }
        }
        return count + 1;
    }
}

Explanation:

Lower Bound (left) is initially set to the maximum element in the array, and it increases if a split with the current mid isn’t feasible.
Upper Bound (right) is initially set to the total sum of the array, and it decreases if a split with the current mid is feasible.

This method ensures that you are narrowing down the possible values of the “largest sum” until you find the minimum feasible one.

Applying the Concept to Other Scenarios

Understanding and applying the concepts of upper and lower bounds can be extended to many other problems, especially those involving optimization or partitioning. Here are a few scenarios:

Finding the Smallest/Largest Feasible Value: In many optimization problems, binary search over possible results, paired with feasibility checks, can be extremely efficient.
Range Queries: Lower and upper bounds are crucial in problems that ask for the range of indices that satisfy certain conditions.
Insertion in Sorted Data: These bounds help determine the correct position to insert new elements while maintaining order.

By mastering binary search, you can tackle a wide variety of questions and optimizations. Binary search is not only a fundamental algorithm in computer science but also one of the most widely used algorithms in real-world applications. Understanding its workings and how slight variations can help you achieve your desired result is incredibly beneficial in practical scenarios.