Binary Search on Answer Technique in DSA C++

Mental Model

We guess an answer and check if it works, then adjust the guess up or down until we find the best answer.

Analogy: Imagine trying to find the right temperature to bake a cake by guessing a temperature, baking, and checking if it's done. If it's undercooked, increase the temperature; if burnt, decrease it. Repeat until perfect.

low ← mid -> high
[low]----[mid]----[high]
 ↑      ↑       ↑
 guess  check   limit

Dry Run Walkthrough

Input: array: [2, 3, 5, 9, 14], max allowed sum per subarray = 10; find minimum largest sum to split array into subarrays

Goal: Find the smallest maximum sum possible when splitting the array into subarrays so that no subarray sum exceeds this value

Step 1: Set low to max element 14, high to sum 33, guess mid = (14+33)/2 = 23

low=14, mid=23, high=33

Why: We start searching between the largest single element and total sum

Step 2: Check if array can be split with max subarray sum ≤ 23

Subarrays: [2,3,5,9] sum=19 ≤ 23, [14] sum=14 ≤ 23

Why: 23 works because we can split into 2 subarrays without exceeding 23

Step 3: Since 23 works, try smaller max sum by setting high = mid = 23

low=14, high=23

Why: Try to find smaller max sum to optimize answer

Step 4: Guess mid = (14+23)/2 = 18, check feasibility

Check subarrays with max sum ≤ 18

Why: Test if smaller max sum 18 is possible

Step 5: Split: [2,3,5,9] sum=19 > 18, so split earlier: [2,3,5] sum=10 ≤ 18, next subarray [9,14] sum=23 > 18

Cannot split into valid subarrays with max sum ≤ 18

Why: 18 too small, need to increase low

Step 6: Set low = mid + 1 = 19

low=19, high=23

Why: Increase low to find feasible max sum

Step 7: Guess mid = (19+23)/2 = 21, check feasibility

Check subarrays with max sum ≤ 21

Why: Test if 21 works

Step 8: Split: [2,3,5,9] sum=19 ≤ 21, [14] sum=14 ≤ 21, works

Feasible with max sum 21

Why: Try smaller max sum by setting high = 21

Step 9: Set high = 21

low=19, high=21

Why: Try to find smaller max sum

Step 10: Guess mid = (19+21)/2 = 20, check feasibility

Check subarrays with max sum ≤ 20

Why: Test if 20 works

Step 11: Split: [2,3,5,9] sum=19 ≤ 20, [14] sum=14 ≤ 20, works

Feasible with max sum 20

Why: Try smaller max sum by setting high = 20

Step 12: Set high = 20

low=19, high=20

Why: Try to find smaller max sum

Step 13: Guess mid = (19+20)/2 = 19, check feasibility

Check subarrays with max sum ≤ 19

Why: Test if 19 works

Step 14: Split: [2,3,5,9] sum=19 ≤ 19, [14] sum=14 ≤ 19, works

Feasible with max sum 19

Why: Try smaller max sum by setting high = 19

Step 15: Set high = 19

low=19, high=19

Why: low equals high, search ends

Result:

Final answer: 19
Array split with max subarray sum 19: [2,3,5,9] and [14]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

bool canSplit(const vector<int>& nums, int maxSum) {
    int currentSum = 0;
    int subarrays = 1;
    for (int num : nums) {
        if (num > maxSum) return false; // single element too big
        if (currentSum + num <= maxSum) {
            currentSum += num; // add to current subarray
        } else {
            subarrays++; // start new subarray
            currentSum = num;
        }
    }
    return subarrays <= 2; // check if splits within allowed count
}

int binarySearchAnswer(const vector<int>& nums) {
    int low = *max_element(nums.begin(), nums.end());
    int high = accumulate(nums.begin(), nums.end(), 0);
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canSplit(nums, mid)) {
            high = mid; // try smaller max sum
        } else {
            low = mid + 1; // increase min sum
        }
    }
    return low;
}

int main() {
    vector<int> nums = {2, 3, 5, 9, 14};
    int result = binarySearchAnswer(nums);
    cout << result << endl;
    return 0;
}

if (num > maxSum) return false; // single element too big

guard against impossible max sum smaller than any element

if (currentSum + num <= maxSum) { currentSum += num; } else { subarrays++; currentSum = num; }

split array when adding next element exceeds maxSum

return subarrays <= 2;

check if number of subarrays is within allowed limit

while (low < high) { int mid = low + (high - low) / 2; if (canSplit(nums, mid)) { high = mid; } else { low = mid + 1; } }

binary search on answer space adjusting low/high based on feasibility

Output

19

Complexity Analysis

Time: O(n log S) because each binary search step does a linear check over n elements, and S is the range between max element and sum

Space: O(1) because only a few variables are used, no extra data structures proportional to input

vs Alternative: Naive approach tries all sums from max element to total sum, which is O(n * S) and much slower

Edge Cases

Array with one element

Returns that element as minimum max sum

DSA C++

if (num > maxSum) return false;

All elements equal

Splits evenly, binary search finds exact max sum

DSA C++

while (low < high) { ... }

Max sum smaller than any element

canSplit returns false immediately

DSA C++

if (num > maxSum) return false;

When to Use This Pattern

When a problem asks for an optimal numeric answer that can be checked for feasibility, use binary search on the answer space to efficiently find it.

Common Mistakes

Mistake: Not setting low to max element, causing invalid guesses
Fix: Initialize low as the maximum element in the array

Mistake: Not checking feasibility correctly, allowing invalid splits
Fix: Implement canSplit to count subarrays and compare with allowed limit

Summary

Finds the smallest value that satisfies a feasibility condition by guessing and checking.

Use when the answer is numeric and can be tested with a yes/no feasibility function.

The key is to binary search over the answer range, not the input data.