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: Like guessing the right temperature to bake a cake by trying a temperature, seeing if it cooks well, then adjusting higher or lower until perfect.

Low ← mid -> High
  |      ↑      |
  v             v
 [0] ... [mid] ... [max]

Dry Run Walkthrough

Input: Find minimum maximum weight capacity to ship packages within 3 days. Packages weights: [1,2,3,4,5,6,7,8,9,10]

Goal: Find the smallest ship capacity that can ship all packages in 3 days.

Step 1: Set low to max package weight 10, high to sum of all weights 55, guess mid = (10+55)/2 = 32

Low=10 ← Mid=32 -> High=55

Why: We start guessing capacity between the heaviest package and total weight.

Step 2: Check if capacity 32 can ship in 3 days: day1(1+2+3+4+5+6+7=28), day2(8+9+10=27) -> 2 days needed

Capacity=32 works with 2 days

Why: Capacity 32 is enough, try smaller capacity to find minimum.

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

Low=10 ← Mid=21 -> High=32

Why: Try smaller capacity to see if it still works.

Step 4: Check capacity 21: day1(1+2+3+4+5+6=21), day2(7+8=15), day3(9+10=19) -> 3 days needed

Capacity=21 works with 3 days

Why: Capacity 21 still works, try smaller.

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

Low=10 ← Mid=15 -> High=21

Why: Try smaller capacity again.

Step 6: Check capacity 15: day1(1+2+3+4+5=15), day2(6+7=13), day3(8), day4(9), day5(10) -> 5 days needed

Capacity=15 needs 5 days, too many

Why: Capacity 15 too small, need more days than allowed.

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

Low=16 ← Mid=18 -> High=21

Why: Increase capacity to reduce days.

Step 8: Check capacity 18: day1(1+2+3+4+5=15), day2(6+7=13), day3(8+9=17), day4(10=10) -> 4 days needed

Capacity=18 needs 4 days, too many

Why: Still too small, increase capacity.

Step 9: Set low = mid + 1 = 19, guess mid = (19+21)/2 = 20

Low=19 ← Mid=20 -> High=21

Why: Try capacity 20.

Step 10: Check capacity 20: day1(1+2+3+4+5=15), day2(6+7=13), day3(8+9=17), day4(10=10) -> 4 days needed

Capacity=20 needs 4 days, too many

Why: Capacity 20 still too small.

Step 11: Set low = mid + 1 = 21, guess mid = (21+21)/2 = 21

Low=21 ← Mid=21 -> High=21

Why: Try capacity 21 again.

Step 12: Check capacity 21 again: works in 3 days as before

Capacity=21 works with 3 days

Why: Capacity 21 is minimum that works.

Result:

Final capacity = 21
Packages shipped in 3 days with capacity 21.

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class BinarySearchOnAnswer {
    // Check if we can ship all packages within days with given capacity
    static bool CanShip(int[] weights, int days, int capacity) {
        int dayCount = 1;
        int currentLoad = 0;
        foreach (int w in weights) {
            if (currentLoad + w <= capacity) {
                currentLoad += w; // add package to current day
            } else {
                dayCount++; // need next day
                currentLoad = w; // start new day load
                if (dayCount > days) return false; // too many days
            }
        }
        return true; // shipped within days
    }

    // Find minimum capacity to ship packages within days
    static int ShipWithinDays(int[] weights, int days) {
        int low = 0;
        int high = 0;
        foreach (int w in weights) {
            if (w > low) low = w; // max single package weight
            high += w; // sum of all weights
        }

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (CanShip(weights, days, mid)) {
                high = mid; // try smaller capacity
            } else {
                low = mid + 1; // increase capacity
            }
        }
        return low;
    }

    static void Main() {
        int[] weights = {1,2,3,4,5,6,7,8,9,10};
        int days = 3;
        int result = ShipWithinDays(weights, days);
        Console.WriteLine(result);
    }
}

if (currentLoad + w <= capacity) { currentLoad += w; } else { dayCount++; currentLoad = w; if (dayCount > days) return false; }

Accumulate package weights per day, start new day if capacity exceeded, stop if days exceeded

int low = max package weight; int high = sum of all weights;

Set search range for capacity between heaviest package and total weight

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

Binary search to find minimum capacity that can ship in given days

Output

21

Complexity Analysis

Time: O(n log S) because we do binary search on capacity range S and check all n packages each time

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

vs Alternative: Naive approach tries all capacities from max weight to sum, which is O(n*S) and very slow

Edge Cases

Single package

Capacity equals package weight, returns immediately

DSA C#

if (w > low) low = w;

Days equal to number of packages

Minimum capacity is max package weight because each package can ship alone

DSA C#

if (CanShip(weights, days, mid)) { high = mid; }

Days is 1

Capacity must be sum of all packages

DSA C#

int high = sum of all weights;

When to Use This Pattern

When a problem asks for an optimal numeric answer under constraints and checking feasibility is easier than direct calculation, use binary search on answer to guess and verify efficiently.

Common Mistakes

Mistake: Setting low to 0 instead of max package weight causes wrong guesses below feasible capacity.
Fix: Initialize low to max package weight to ensure capacity can hold largest package.

Mistake: Not updating low to mid + 1 when capacity is too small causes infinite loop.
Fix: Increase low to mid + 1 when capacity guess fails to progress search.

Summary

It finds the best numeric answer by guessing and checking feasibility using binary search.

Use it when you can check if a guessed answer works but can't directly compute the answer.

The key insight is to turn an optimization problem into a yes/no question and binary search over possible answers.

Practice

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

easy

A. We sort the input array and then perform a binary search on the sorted array.

B. We guess an answer and check if it satisfies the problem, then adjust the guess using binary search.

C. We use binary search to find the maximum element in an unsorted array.

D. We apply binary search to find the first occurrence of a target value in a list.

Solution

1. Step 1: Understand the technique

   Binary Search on Answer guesses a possible solution and verifies if it meets the problem's conditions. If valid, adjust the guess (smaller/larger) using binary search to find the optimal answer.

2. Final Answer:

   We guess an answer and check if it satisfies the problem, then adjust the guess using binary search. -> Option B

3. Quick Check:

   Guess and verify with binary search = B [OK]

Hint: Guess answer, check condition, adjust guess with binary search [OK]

Common Mistakes:

• Confusing binary search on answer with normal binary search on array
• Thinking it only works on sorted arrays
• Not verifying the guessed answer properly

2. Which of the following is the correct C# syntax to start a binary search on answer between low and high?

easy

A. do { int mid = (low - high) / 2; } while (low < high);

B. for (int mid = low; mid <= high; mid++) { }

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

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

Solution

1. Step 1: Identify correct loop and mid calculation

   The binary search loop uses while (low <= high) and mid = (low + high) / 2 with integer division.

2. Final Answer:

   while (low <= high) { int mid = (low + high) / 2; } -> Option D

3. Quick Check:

   Correct binary search loop syntax = A [OK]

Hint: Use while(low <= high) and mid = (low + high) / 2 [OK]

Common Mistakes:

• Using for loop instead of while
• Incorrect mid calculation like (low - high)/2
• Using if instead of loop

3. Consider the following C# code snippet using binary search on answer to find minimum maximum load:

int low = 10, high = 50;
while (low <= high) {
  int mid = (low + high) / 2;
  if (IsPossible(mid))
    high = mid - 1;
  else
    low = mid + 1;
}
Console.WriteLine(low);

If IsPossible(30) returns true and IsPossible(20) returns false, what will be printed?

medium

A. 10

B. 30

C. 21

D. 20

Solution

1. Step 1: Trace binary search behavior

   IsPossible(mid) true means valid (try smaller, high=mid-1); false means invalid (low=mid+1). Given IsPossible(30)=true, IsPossible(20)=false, assuming monotonicity the search converges to smallest valid at 21.

2. Final Answer:

   21 -> Option C

3. Quick Check:

   Minimum valid answer after binary search = 21 [OK]

Hint: Answer is lowest valid mid after binary search ends [OK]

Common Mistakes:

• Printing high instead of low after loop
• Confusing true/false meaning of IsPossible
• Not updating low and high correctly

4. The following code tries to find the minimum maximum load using binary search on answer. What is the bug?

int low = 0, high = maxLoad;
while (low < high) {
  int mid = (low + high) / 2;
  if (IsPossible(mid))
    low = mid;
  else
    high = mid - 1;
}
Console.WriteLine(low);

medium

A. When IsPossible(mid) is true, 'low' should be set to 'mid + 1' instead of 'mid'.

B. When IsPossible(mid) is true, 'high' should be set to 'mid - 1' instead of 'low'.

C. The condition should be 'while (low <= high)' instead of 'while (low < high)'.

D. The mid calculation should be 'mid = low + (high - low) / 2' to avoid overflow.

Solution

1. Step 1: Identify incorrect update causing infinite loop

   When IsPossible(mid) true, low = mid risks no progress (infinite loop if low == mid); should set low = mid + 1 to advance.

2. Final Answer:

   When IsPossible(mid) is true, 'low' should be set to 'mid + 1' instead of 'mid'. -> Option A

3. Quick Check:

   Increment low by 1 to avoid infinite loop [OK]

Hint: Increment low by 1 when condition true to avoid infinite loop [OK]

Common Mistakes:

• Not incrementing low causing infinite loop
• Confusing when to move low or high
• Ignoring loop condition correctness

5. You want to split an array of weights into k contiguous subarrays so that the maximum sum among these subarrays is minimized. Which approach correctly uses binary search on answer to solve this?

hard

A. Binary search between max weight and sum of all weights; check if array can be split into ≤ k parts with max sum ≤ mid.

B. Sort the array and binary search for the kth largest weight.

C. Use binary search on the array indices to find the split points directly.

D. Apply binary search on the number of subarrays from 1 to k.

Solution

1. Step 1: Define search space and feasibility check

   Binary search from max weight (min possible max sum) to total sum; for mid, check if can split into ≤ k contiguous subarrays each with sum ≤ mid. If yes, try smaller mid; else larger.

2. Final Answer:

   Binary search between max weight and sum of all weights; check if array can be split into ≤ k parts with max sum ≤ mid. -> Option A

3. Quick Check:

   Search answer range and verify splits ≤ k [OK]

Hint: Search between max element and total sum, check splits ≤ k [OK]

Common Mistakes:

• Binary searching on indices instead of answer range
• Not checking contiguous subarray sums properly
• Sorting array unnecessarily