Binary Search on Answer Technique in DSA Python

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 highest floor from which an egg won't break by dropping it and adjusting your guess based on whether it breaks or not.

Answer range: [low] ---- mid ---- [high]
Check if mid is valid -> move low or high accordingly
Repeat until low meets high

Dry Run Walkthrough

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

Goal: Find the smallest maximum subarray sum possible by splitting into 2 parts

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 with the smallest possible max sum and the largest possible max sum

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

Subarrays: [7,2,5], [10,8]

Why: We need to see if mid=21 is a valid max sum to split into 2 parts

Step 3: Since we needed 2 subarrays and allowed 2, mid=21 is valid, try smaller max sum by setting high=21

low=10, high=21

Why: Try to find smaller max sum to minimize answer

Step 4: Guess new mid = (10+21)//2 = 15, check splits with max sum ≤15

mid=15

Why: Narrow down search range

Step 5: Split array: [7,2,5] sum=14 ≤15, 14+10=24 >15 so split before 10, then [10]≤15 but 10+8=18>15 split Subarrays: [7,2,5], [10], [8]

3 subarrays needed > 2 allowed

Why: mid=15 too small, need more subarrays than allowed

Step 6: mid=15 invalid, increase low to mid+1=16

low=16, high=21

Why: Try larger max sum to reduce number of subarrays

Step 7: Guess mid = (16+21)//2=18, check splits with max sum ≤18

mid=18

Why: Continue binary search

Step 8: Check if array can be split into ≤2 subarrays with max sum ≤18

Subarrays: [7,2,5], [10,8]

Why: We need to see if mid=18 is a valid max sum to split into 2 parts

Step 9: Since we needed 2 subarrays and allowed 2, mid=18 is valid, try smaller max sum by setting high=18

low=16, high=18

Why: Try to find smaller max sum to minimize answer

Step 10: Guess new mid = (16+18)//2 = 17, check splits with max sum ≤17

mid=17

Why: Narrow down search range

Step 11: Split array: [7,2,5] sum=14 ≤17, 14+10=24 >17 so split before 10, [10]≤17 but 10+8=18>17 split Subarrays: [7,2,5], [10], [8]

3 subarrays needed > 2 allowed

Why: mid=17 too small, need more subarrays than allowed

Step 12: mid=17 invalid, increase low to mid+1=18

low=18, high=18

Why: Try larger max sum to reduce number of subarrays

Step 13: Now low == high == 18, stop search

Answer = 18

Why: Found smallest max sum to split into 2 subarrays

Result:

Final answer: 18

Annotated Code

DSA Python

class Solution:
    def splitArray(self, nums, m):
        def can_split(max_sum):
            current_sum = 0
            count = 1
            for num in nums:
                if current_sum + num > max_sum:
                    count += 1
                    current_sum = num
                    if count > m:
                        return False
                else:
                    current_sum += num
            return True

        low, high = max(nums), sum(nums)
        while low < high:
            mid = (low + high) // 2
            if can_split(mid):
                high = mid
            else:
                low = mid + 1
        return low


if __name__ == '__main__':
    nums = [7, 2, 5, 10, 8]
    m = 2
    sol = Solution()
    print(sol.splitArray(nums, m))

for num in nums:

iterate over each number to accumulate sums

if current_sum + num > max_sum:

check if adding num exceeds allowed max sum

count += 1

start a new subarray because current sum exceeded max

if count > m:

if subarrays needed exceed allowed m, return False

while low < high:

binary search loop to narrow down answer range

if can_split(mid):

if mid is valid max sum, try smaller values

else: low = mid + 1

if mid invalid, increase low to try larger sums

Output

18

Complexity Analysis

Time: O(n log S) where n is array length and S is sum of elements, because we binary search over sum range and check splits in O(n)

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

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 answer since only one subarray possible

DSA Python

low, high = max(nums), sum(nums)

m equals array length

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

DSA Python

if count > m: return False

All elements equal

Binary search narrows answer to that element value

DSA Python

while low < high:

When to Use This Pattern

When a problem asks for an optimal numeric answer that can be checked with a yes/no condition, use binary search on answer to efficiently find it.

Common Mistakes

Mistake: Not setting low to max element and high to sum of array
Fix: Initialize low = max(nums) and high = sum(nums) to cover all possible answers

Mistake: Not correctly counting subarrays in can_split function
Fix: Increment count only when current sum exceeds mid and reset current sum

Summary

Finds the smallest or largest 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 turn the problem into a yes/no check and binary search over the answer range.

Practice

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

easy

A. We apply binary search to split the input into two equal halves repeatedly.

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

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

D. We use binary search to find the middle element of a sorted list.

Solution

1. Step 1: Understand the technique's purpose

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

2. Step 2: Adjust guess based on check

   If the guess is valid, we try smaller or larger guesses using binary search to find the optimal answer.

3. Final Answer:

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

4. Quick Check:

   Guess and check with binary search = We guess an answer and check if it satisfies the problem, then adjust the guess using binary search. [OK]

Hint: Think of guessing answers and narrowing down with binary search [OK]

Common Mistakes:

• Confusing with normal binary search on sorted arrays
• Thinking it only finds elements, not answers
• Ignoring the check step after guessing

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

easy

A. while low <= high:
mid = (low + high) // 2

B. for mid in range(low, high):

C. if low < high:
mid = (low + high) / 2

D. while low < high:
mid = (low + high) // 2 + 1

Solution

1. Step 1: Identify the binary search loop condition

   Binary search typically uses a while loop with condition low <= high to cover all possible values.

2. Step 2: Calculate mid correctly

   Mid is calculated as integer division (low + high) // 2 to get the middle integer index or value.

3. Final Answer:

   while low <= high: mid = (low + high) // 2 -> Option A

4. Quick Check:

   Correct loop and mid calculation = while low <= high: mid = (low + high) // 2 [OK]

Hint: Use while low <= high and integer division for mid [OK]

Common Mistakes:

• Using for loop instead of while
• Using float division instead of integer division
• Wrong loop condition like low < high

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

def can_split(nums, m, max_load):
    count, current_sum = 1, 0
    for num in nums:
        if current_sum + num > max_load:
            count += 1
            current_sum = num
            if count > m:
                return False
        else:
            current_sum += num
    return True

nums = [7, 2, 5, 10, 8]
m = 2
low, high = max(nums), sum(nums)
while low < high:
    mid = (low + high) // 2
    if can_split(nums, m, mid):
        high = mid
    else:
        low = mid + 1
print(low)

What is the output of this code?

medium

A. 15

B. 18

C. 20

D. 10

Solution

1. Step 1: Understand the problem and initial bounds

   We want to split nums into 2 subarrays minimizing the maximum sum. low = max(nums) = 10, high = sum(nums) = 32.

2. Step 2: Trace binary search iterations

   - mid=21: True ([7,2,5]=14, [10,8]=18 <=21), high=21
   - mid=15: False (requires 3 subarrays), low=16
   - mid=18: True, high=18
   - mid=17: False, low=18
   Final low=18.

3. Final Answer:

   18 -> Option B

4. Quick Check:

   Minimum max load for 2 splits = 18 [OK]

Hint: Check mid as max load and validate splits [OK]

Common Mistakes:

• Not setting low as max element
• Confusing count of subarrays
• Off-by-one errors in loop conditions

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

def can_finish(tasks, workers, max_time):
    count = 1
    current_time = 0
    for t in tasks:
        if t > max_time:
            return False
        if current_time + t <= max_time:
            current_time += t
        else:
            count += 1
            current_time = t
    return count <= workers

tasks = [3, 6, 7, 11]
workers = 2
low, high = 0, sum(tasks)
while low < high:
    mid = (low + high) // 2
    if can_finish(tasks, workers, mid):
        high = mid
    else:
        low = mid + 1
print(low)

medium

A. The current_time should reset to 0 instead of t after incrementing count

B. The function should return count < workers instead of <= workers

C. The loop condition should be while low <= high

D. Initial low should be max(tasks), not 0

Solution

1. Step 1: Check initial binary search bounds

   Low is set to 0, but minimum max_time must be at least max(tasks) because no task can be split.

2. Step 2: Understand effect of wrong low

   Starting low at 0 causes unnecessary checks and may cause infinite loop or wrong answer.

3. Final Answer:

   Initial low should be max(tasks), not 0 -> Option D

4. Quick Check:

   Low bound must be max task time [OK]

Hint: Set low to max task time to avoid invalid guesses [OK]

Common Mistakes:

• Setting low to 0 instead of max(tasks)
• Wrong loop condition causing infinite loops
• Resetting current_time incorrectly

5. You want to find the minimum largest sum when splitting an array nums into k subarrays. However, some elements can be zero or negative. How should you modify the binary search on answer approach to handle this correctly?

hard

A. Set low to min(nums) and high to sum of absolute values of nums, then apply binary search with adjusted checks.

B. Ignore negative values and treat them as zero, then apply normal binary search on answer.

C. Use normal binary search with low as max(nums) and high as sum(nums) without changes.

D. Sort the array first, then apply binary search on answer with low as 0 and high as sum(nums).

Solution

1. Step 1: Identify problem with negative and zero values

   Negative values can reduce sums, so max(nums) may be negative or zero, and sum(nums) may be less than max(nums).

2. Step 2: Adjust binary search bounds

   Set low to minimum element (which can be negative) and high to sum of absolute values to cover all possible sums.

3. Step 3: Modify check function

   Check function must handle negative sums correctly and validate splits accordingly.

4. Final Answer:

   Set low to min(nums) and high to sum of absolute values of nums, then apply binary search with adjusted checks. -> Option A

5. Quick Check:

   Adjust bounds for negatives and zeros [OK]

Hint: Adjust low/high bounds when negatives exist [OK]

Common Mistakes:

• Using max(nums) as low when negatives exist
• Ignoring negative values in sums
• Assuming sums are always positive