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

Practice

1. What is the main idea behind the Binary Search on Answer technique?

easy

A. We guess an answer and use binary search to find the smallest or largest valid value.

B. We sort the array and then apply binary search to find an element.

C. We use binary search to find the middle element in a sorted list.

D. We apply binary search to split the array into two halves repeatedly.

Solution

1. Step 1: Understand the technique's goal

   Binary Search on Answer guesses a possible answer and checks if it meets the problem's conditions.

2. Step 2: Use binary search on the answer range

   We narrow down the answer by checking mid-values until we find the smallest or largest valid answer.

3. Final Answer:

   We guess an answer and use binary search to find the smallest or largest valid value. -> Option A

4. Quick Check:

   Binary Search on Answer = Guess and check with binary search [OK]

Hint: Think of binary searching the answer, not the array [OK]

Common Mistakes:

• Confusing it with normal binary search on sorted arrays
• Trying to binary search elements instead of answer values
• Not defining a valid check function for guesses

2. Which of the following is the correct syntax to start a binary search on answer in JavaScript for a range from low to high?

easy

A. for (let mid = low; mid <= high; mid++) { }

B. while (low <= high) { let mid = Math.floor((low + high) / 2); }

C. if (low < high) { mid = (low + high) / 2; }

D. do { mid = (low + high) / 2; } while (low < high);

Solution

1. Step 1: Identify the binary search loop structure

   Binary search uses a while loop checking low <= high to continue searching.

2. Step 2: Calculate mid correctly

   Mid is calculated as Math.floor((low + high) / 2) to get the middle integer index.

3. Final Answer:

   while (low <= high) { let mid = Math.floor((low + high) / 2); } -> Option B

4. Quick Check:

   Correct binary search loop syntax = while (low <= high) { let mid = Math.floor((low + high) / 2); } [OK]

Hint: Use while loop with low <= high and floor mid [OK]

Common Mistakes:

• Using for loop instead of while for binary search
• Not flooring mid value causing float indices
• Using incorrect loop conditions like low < high

3. Consider the following code snippet using binary search on answer to find the minimum capacity to ship packages within D days:

function canShip(weights, capacity, D) {
  let days = 1, currentLoad = 0;
  for (let w of weights) {
    if (currentLoad + w > capacity) {
      days++;
      currentLoad = 0;
    }
    currentLoad += w;
  }
  return days <= D;
}

function shipWithinDays(weights, D) {
  let low = Math.max(...weights);
  let high = weights.reduce((a, b) => a + b, 0);
  while (low < high) {
    let mid = Math.floor((low + high) / 2);
    if (canShip(weights, mid, D)) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  return low;
}

console.log(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5));

What is the output of this code?

medium

A. 20

B. 10

C. 15

D. 5

Solution

1. Step 1: Understand the problem and code

   The code finds the minimum ship capacity to ship weights in 5 days. It uses binary search between max weight (10) and sum (55).

2. Step 2: Trace binary search narrowing

   Checking mid values, the minimum capacity that allows shipping in 5 days is 15.

3. Final Answer:

   15 -> Option C

4. Quick Check:

   Minimum capacity to ship in 5 days = 15 [OK]

Hint: Check max weight and sum, binary search between them [OK]

Common Mistakes:

• Choosing max weight (10) as answer instead of minimum capacity
• Choosing total sum (55) instead of minimum valid capacity
• Misunderstanding the days condition in canShip

4. The following code tries to find the maximum length of a rope to cut at least k pieces using binary search on answer. Find the bug:

function maxLength(ropes, k) {
  let low = 0;
  let high = Math.max(...ropes);
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    let count = 0;
    for (let r of ropes) {
      count += Math.floor(r / mid);
    }
    if (count >= k) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return high;
}

medium

A. Using while (low <= high) instead of while (low < high) is wrong.

B. Not sorting ropes before binary search causes wrong answer.

C. Returning high instead of low is incorrect.

D. Starting low from 0 causes division by zero error.

Solution

1. Step 1: Identify potential division by zero

   Starting low at 0 means mid can be 0, causing division by zero in Math.floor(r / mid).

2. Step 2: Fix low initialization

   Set low to 1 to avoid division by zero and ensure valid rope length guesses.

3. Final Answer:

   Starting low from 0 causes division by zero error. -> Option D

4. Quick Check:

   low = 0 causes divide by zero [OK]

Hint: Avoid zero as divisor in binary search on answer [OK]

Common Mistakes:

• Ignoring division by zero possibility
• Changing loop condition unnecessarily
• Returning wrong boundary without reason

5. You want to find the minimum maximum time to complete all tasks by k workers, where each worker can do consecutive tasks only. Given task times array tasks, how would you apply binary search on answer to solve this?

Choose the best approach:

hard

A. Binary search on time range; check if tasks can be split into ≤ k groups with max sum ≤ mid.

B. Sort tasks and binary search for the smallest task time.

C. Use binary search on number of tasks each worker gets, ignoring task times.

D. Apply binary search on total tasks count to assign tasks evenly.

Solution

1. Step 1: Define the answer range

   The minimum max time is at least max task time, max is sum of all tasks.

2. Step 2: Check feasibility with mid value

   Check if tasks can be split into ≤ k groups where each group's sum ≤ mid.

3. Step 3: Use binary search to narrow answer

   Adjust low and high based on feasibility until minimum max time is found.

4. Final Answer:

   Binary search on time range; check if tasks can be split into ≤ k groups with max sum ≤ mid. -> Option A

5. Quick Check:

   Binary search on max time with group feasibility check [OK]

Hint: Binary search answer range, check group splits feasibility [OK]

Common Mistakes:

• Binary searching on tasks count instead of time
• Ignoring consecutive task grouping constraint
• Sorting tasks unnecessarily