Binary Search on Answer Technique in DSA Javascript

Mental Model

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

Analogy: Imagine guessing the weight of a box by lifting it. If it feels too heavy, guess a lighter weight; if too light, guess heavier. Repeat until you find the exact weight you can lift comfortably.

Range of answers: [low] ---- mid ---- [high]
Check if mid is valid -> move low or high accordingly
Repeat until low meets high

Dry Run Walkthrough

Input: Find the minimum largest sum when splitting array [7,2,5,10,8] into 2 subarrays

Goal: Find the smallest maximum sum among 2 subarrays after splitting

Step 1: Set low to max element 10, high to sum 32, guess mid = (10+32)//2 = 21

low=10, mid=21, high=32

Why: We start guessing the answer between max single element and total sum

Step 2: Check if we can split into 2 subarrays with max sum ≤ 21: [7,2,5] sum=14, [10,8] sum=18 -> valid

Splits possible with max sum 21

Why: Mid is valid, so try smaller max sum to find minimum

Step 3: Set high = mid = 21, guess new mid = (10+21)//2 = 15

low=10, mid=15, high=21

Why: Try smaller max sum to see if still valid

Step 4: Check splits with max sum ≤ 15: [7,2,5] sum=14, next 10 alone (10), next 8 alone (8) -> need 3 subarrays, invalid

Splits need 3 subarrays, more than allowed 2

Why: Mid too small, increase low to find valid max sum

Step 5: Set low = mid + 1 = 16, guess new mid = (16+21)//2 = 18

low=16, mid=18, high=21

Why: Try a bigger max sum to allow fewer splits

Step 6: Check splits with max sum ≤ 18: [7,2,5] sum=14, [10,8] sum=18 -> valid

Splits possible with max sum 18

Why: Mid valid, try smaller max sum

Step 7: Set high = mid = 18, guess new mid = (16+18)//2 = 17

low=16, mid=17, high=18

Why: Try smaller max sum again

Step 8: Check splits with max sum ≤ 17: [7,2,5] sum=14, next 10 alone (10), next 8 alone (8) -> need 3 subarrays, invalid

Splits need 3 subarrays, invalid

Why: Mid too small, increase low

Step 9: Set low = mid + 1 = 18, now low == high == 18, stop

low=18, high=18

Why: Low meets high, found minimum largest sum

Result:

Final answer: 18
Splits: [7,2,5] and [10,8]

Annotated Code

DSA Javascript

class Solution {
  // Check if array can be split into <= m subarrays with max sum <= mid
  canSplit(nums, m, mid) {
    let count = 1;
    let currentSum = 0;
    for (const num of nums) {
      if (currentSum + num <= mid) {
        currentSum += num; // add to current subarray
      } else {
        count++; // start new subarray
        currentSum = num;
        if (count > m) return false; // too many subarrays
      }
    }
    return true;
  }

  splitArray(nums, m) {
    let low = Math.max(...nums); // minimum possible max sum
    let high = nums.reduce((a, b) => a + b, 0); // maximum possible max sum

    while (low < high) {
      const mid = Math.floor((low + high) / 2);
      if (this.canSplit(nums, m, mid)) {
        high = mid; // try smaller max sum
      } else {
        low = mid + 1; // increase max sum
      }
    }
    return low;
  }
}

// Driver code
const sol = new Solution();
const nums = [7, 2, 5, 10, 8];
const m = 2;
const result = sol.splitArray(nums, m);
console.log(result);

if (currentSum + num <= mid) { currentSum += num; } else { count++; currentSum = num; if (count > m) return false; }

Check if current number fits in current subarray or start new subarray; fail if too many subarrays

while (low < high) { const mid = Math.floor((low + high) / 2); if (this.canSplit(nums, m, mid)) { high = mid; } else { low = mid + 1; } }

Binary search on answer range, narrowing down to minimum valid max sum

Output

18

Complexity Analysis

Time: O(n log S) because we do binary search on the sum range S, and each check scans all n elements

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Naive approach tries all sums and splits, which is exponential; binary search on answer reduces it to logarithmic steps

Edge Cases

Array with one element

Returns that element as the minimum largest sum

DSA Javascript

let low = Math.max(...nums);

Number of subarrays equals array length

Minimum largest sum is max element because each element is its own subarray

DSA Javascript

if (count > m) return false;

All elements equal

Splits evenly, binary search finds exact equal sum

DSA Javascript

while (low < high) { ... }

When to Use This Pattern

When a problem asks for an optimal numeric answer that can be checked by a yes/no condition, use binary search on answer to guess and verify efficiently.

Common Mistakes

Mistake: Setting low to 0 instead of max element causes invalid guesses
Fix: Set low to the maximum element to ensure guesses are valid

Mistake: Not updating low to mid + 1 when mid is invalid causes infinite loop
Fix: Increase low to mid + 1 when mid guess fails the condition

Summary

Finds the best numeric answer by guessing and checking with binary search

Use when answer is a number and you can check if a guess is valid

The key is to narrow the answer range by testing midpoints and adjusting bounds