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 guessing the weight of a box by trying different weights on a scale. If the guess is too heavy, you try lighter weights; if too light, you try heavier weights until you find the exact weight.

low = 0
mid = ?
high = max

Check if mid is valid -> adjust low or high

[low] ---- [mid] ---- [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 the 2 subarrays after splitting

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

low=10, mid=21, high=32

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

Step 2: Check if we can split into 2 subarrays with max sum ≤ 21

Subarrays: [7,2,5] sum=14, [10,8] sum=18

Why: Splitting is possible with max sum 21, so try smaller max sum

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

low=10, mid=15, high=21

Why: Try to find smaller max sum that still works

Step 4: Check if split possible with max sum ≤ 15

Subarrays: [7,2,5] sum=14, [10] sum=10, [8] sum=8 -> 3 subarrays needed

Why: Need 3 subarrays, more than allowed 2, so max sum too small

Step 5: Set low = mid + 1 = 16

low=16, mid= (16+21)/2=18, high=21

Why: Increase low to try larger max sum

Step 6: Check if split possible with max sum ≤ 18

Subarrays: [7,2,5] sum=14, [10,8] sum=18

Why: Split possible with 2 subarrays, try smaller max sum

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

low=16, mid=17, high=18

Why: Try smaller max sum

Step 8: Check if split possible with max sum ≤ 17

Subarrays: [7,2,5] sum=14, [10] sum=10, [8] sum=8 -> 3 subarrays needed

Why: Too many subarrays, max sum too small

Step 9: Set low = mid + 1 = 18

low=18, mid= (18+18)/2=18, high=18

Why: Increase low to try larger max sum

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>

// Check if array can be split into at most m subarrays with max sum <= mid
bool canSplit(int* nums, int numsSize, int m, int mid) {
    int currentSum = 0;
    int count = 1; // at least one subarray
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > mid) return false; // single element bigger than mid
        if (currentSum + nums[i] <= mid) {
            currentSum += nums[i]; // add to current subarray
        } else {
            count++; // start new subarray
            currentSum = nums[i];
            if (count > m) return false; // too many subarrays
        }
    }
    return true;
}

int splitArray(int* nums, int numsSize, int m) {
    int low = 0, high = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > low) low = nums[i]; // max element
        high += nums[i]; // sum of all elements
    }
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canSplit(nums, numsSize, m, mid)) {
            high = mid; // try smaller max sum
        } else {
            low = mid + 1; // increase max sum
        }
    }
    return low;
}

int main() {
    int nums[] = {7, 2, 5, 10, 8};
    int size = sizeof(nums) / sizeof(nums[0]);
    int m = 2;
    int result = splitArray(nums, size, m);
    printf("%d\n", result);
    return 0;
}

if (nums[i] > mid) return false; // single element bigger than mid

check if any element alone exceeds mid, making split impossible

if (currentSum + nums[i] <= mid) { currentSum += nums[i]; } else { count++; currentSum = nums[i]; if (count > m) return false; }

accumulate elements in current subarray or start new subarray if sum exceeds mid

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

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

Output

18

Complexity Analysis

Time: O(n log S) where n is array size and S is sum of elements, because each binary search step checks feasibility in O(n) and binary search runs O(log S) times

Space: O(1) because only a few variables are used regardless of input size

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

Edge Cases

Array with one element

Returns that element as the answer since only one subarray is possible

DSA C

if (nums[i] > mid) return false;

m equals array size

Answer is max element because each element can be its own subarray

DSA C

if (nums[i] > mid) return false;

All elements equal

Splitting evenly to minimize max sum works correctly

DSA C

if (currentSum + nums[i] <= mid) { currentSum += nums[i]; } else { count++; currentSum = nums[i]; if (count > m) 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 answer to efficiently find the best value.

Common Mistakes

Mistake: Not setting low to max element initially, causing invalid mid guesses
Fix: Initialize low as the maximum element in the array before binary searching

Mistake: Not checking if a single element exceeds mid in feasibility check
Fix: Add a check to return false if any element is greater than mid

Mistake: Using low <= high in binary search loop causing infinite loop
Fix: Use low < high as loop condition to avoid infinite loop

Summary

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

Use it when you can test if a guess is valid and want to find the smallest or largest valid value.

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

Practice

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

easy

A. Searching for the answer by repeatedly dividing the search space based on feasibility

B. Sorting the array before applying binary search

C. Using binary search only on sorted arrays

D. Applying binary search to find the maximum element in an array

Solution

1. Step 1: Understand the problem context

   Binary Search on Answer is used when the answer lies within a range and we can check feasibility for a candidate answer.

2. Step 2: Explain the technique

   We repeatedly pick a middle value in the answer range and check if it satisfies the problem's conditions, then narrow the range accordingly.

3. Final Answer:

   Searching for the answer by repeatedly dividing the search space based on feasibility -> Option A

4. Quick Check:

   Binary Search on Answer = Divide and check feasibility [OK]

Hint: Think of answer range, not array elements, for binary search [OK]

Common Mistakes:

• Confusing it with normal binary search on arrays
• Trying to apply without a feasibility check
• Assuming answer must be in the input array

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

easy

A. for (int mid = low; mid <= high; mid++) { /* check feasibility */ }

B. do { mid = (low + high) / 2; /* check feasibility */ } while (low < high);

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

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

Solution

1. Step 1: Identify the binary search loop structure

   Binary search uses a while loop with condition low <= high to narrow the search space.

2. Step 2: Confirm calculation of mid and feasibility check

   Mid is calculated as (low + high) / 2 inside the loop, then feasibility is checked to adjust low or high.

3. Final Answer:

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

4. Quick Check:

   Binary search loop = while(low <= high) [OK]

Hint: Use while loop with low <= high for binary search [OK]

Common Mistakes:

• Using for loop instead of while
• Incorrect loop condition like low < high
• Not updating low or high inside loop

3. Consider the following C code snippet using binary search on answer to find the minimum maximum load to split an array into m subarrays:

int canSplit(int* arr, int n, int m, int maxLoad) {
    int count = 1, currentSum = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxLoad) return 0;
        if (currentSum + arr[i] > maxLoad) {
            count++;
            currentSum = arr[i];
        } else {
            currentSum += arr[i];
        }
    }
    return count <= m;
}

int binarySearchAnswer(int* arr, int n, int m) {
    int low = 0, high = 0;
    for (int i = 0; i < n; i++) high += arr[i];
    int ans = high;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (canSplit(arr, n, m, mid)) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return ans;
}

int main() {
    int arr[] = {7, 2, 5, 10, 8};
    int n = 5, m = 2;
    printf("%d", binarySearchAnswer(arr, n, m));
    return 0;
}

What is the output of this program?

medium

A. 18

B. 15

C. 20

D. 10

Solution

1. Step 1: Understand the problem and code logic

   The code finds the minimum maximum load to split the array into 2 subarrays so that the largest sum among subarrays is minimized.

2. Step 2: Dry run with given array

   Possible splits: - [7,2,5] and [10,8] max sums 14 and 18 -> max 18 - [7,2] and [5,10,8] max sums 9 and 23 -> max 23 - [7] and [2,5,10,8] max sums 7 and 25 -> max 25 Minimum max load is 18.

3. Final Answer:

   18 -> Option A

4. Quick Check:

   Minimum max load = 18 [OK]

Hint: Check feasibility by simulating splits, pick minimal max sum [OK]

Common Mistakes:

• Choosing sum of all elements as answer
• Not considering feasibility function logic
• Confusing minimum max load with total sum

4. The following code tries to find the minimum maximum time to complete tasks by binary searching on answer. Identify the bug:

int canComplete(int* tasks, int n, int m, int maxTime) {
    int count = 1, currentTime = 0;
    for (int i = 0; i < n; i++) {
        if (tasks[i] > maxTime) return 0;
        if (currentTime + tasks[i] >= maxTime) {
            count++;
            currentTime = tasks[i];
        } else {
            currentTime += tasks[i];
        }
    }
    return count <= m;
}

medium

A. The count variable should start from 0, not 1

B. The condition should be currentTime + tasks[i] > maxTime, not >= maxTime

C. The function should return count >= m instead of count <= m

D. The loop should run from i = 1 instead of i = 0

Solution

1. Step 1: Analyze the feasibility condition

   The condition currentTime + tasks[i] >= maxTime causes a new segment even when sum equals maxTime, which is incorrect.

2. Step 2: Correct the condition

   It should be currentTime + tasks[i] > maxTime to start a new segment only when sum exceeds maxTime.

3. Final Answer:

   The condition should be currentTime + tasks[i] > maxTime, not >= maxTime -> Option B

4. Quick Check:

   Use > for splitting condition, not >= [OK]

Hint: Use strict greater than (>) to split segments [OK]

Common Mistakes:

• Using >= causes extra segments
• Starting count from 0 instead of 1
• Returning wrong comparison for count and m

5. You want to find the minimum maximum height to cut trees so that the total wood collected is at least m units. Given an array trees[] of heights, which approach correctly applies binary search on answer to solve this problem?

hard

A. Set low = min height, high = max height; check if sum of all trees is >= m; adjust low or high accordingly

B. Sort trees, then binary search for the tree with height closest to m

C. Set low = 0, high = max height in trees; check if cutting at mid yields enough wood; adjust low or high accordingly

D. Use binary search on the array indices to find the tree that yields maximum wood

Solution

1. Step 1: Define the search space for cutting height

   The cutting height can vary from 0 to the tallest tree height.

2. Step 2: Check feasibility by summing wood collected at mid height

   For a candidate mid, sum wood = sum of (tree height - mid) if positive; check if sum >= m.

3. Step 3: Adjust search space based on feasibility

   If enough wood is collected, try higher cut (low = mid + 1) to minimize cut height; else lower cut (high = mid - 1).

4. Final Answer:

   Set low = 0, high = max height in trees; check if cutting at mid yields enough wood; adjust low or high accordingly -> Option C

5. Quick Check:

   Binary search on cut height range with feasibility check [OK]

Hint: Binary search on cutting height, not on tree indices [OK]

Common Mistakes:

• Binary searching on sorted array instead of answer range
• Using sum of all trees without cutting logic
• Confusing indices with answer values