Binary Search on Answer Technique in DSA Python - Execution Trace

Concept Flow - Binary Search on Answer Technique

Set low and high bounds for answer

↓

Calculate mid = (low + high) // 2

↓

Check if mid is a valid answer

↓

Update high = mid

↓

Repeat until low >= high

↓

Return low as answer

Start with a range for the answer, check the middle value, adjust range based on validity, repeat until range narrows to the answer.

Execution Sample

DSA Python

low, high = 1, 10
while low < high:
    mid = (low + high) // 2
    if is_valid(mid):
        high = mid
    else:
        low = mid + 1
return low

This code finds the smallest valid number between 1 and 10 using binary search on the answer.

Execution Table

Step	Operation	low	high	mid	is_valid(mid)?	Action	Range After Action
1	Initialize	1	10				[1, 10]
2	Calculate mid	1	10	5	No	low = mid + 1	[6, 10]
3	Calculate mid	6	10	8	Yes	high = mid	[6, 8]
4	Calculate mid	6	8	7	No	low = mid + 1	[8, 8]
5	Check low < high	8	8			Stop	[8, 8]
6	Return answer	8	8			Answer = 8

💡 Loop stops when low equals high, meaning the smallest valid answer is found.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
low	1	6	6	8	8	8
high	10	10	8	8	8	8
mid		5	8	7

Key Moments - 3 Insights

Why do we update 'low' to mid + 1 when is_valid(mid) is false?

Because mid is not a valid answer, so the smallest valid answer must be greater than mid. This is shown in step 2 and 4 where low moves past mid.

Why do we update 'high' to mid when is_valid(mid) is true?

Because mid might be the smallest valid answer or there might be a smaller one. So we keep mid in the range by setting high = mid, as seen in step 3.

Why does the loop stop when low equals high?

Because the search range has narrowed to a single number, which must be the smallest valid answer. This is shown in step 5.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'mid' at step 3?

A 5

B 8

C 7

D 6

💡 Hint

Check the 'mid' column in the execution table row for step 3.

At which step does the condition 'is_valid(mid)' return true for the first time?

A Step 4

B Step 2

C Step 3

D Step 5

💡 Hint

Look at the 'is_valid(mid)?' column in the execution table.

If 'is_valid(mid)' was true at step 2, what would be the new value of 'high' after that step?

A 5

B 6

C 10

D 1

💡 Hint

When 'is_valid(mid)' is true, 'high' is set to 'mid'. Check step 3 for reference.

Concept Snapshot

Binary Search on Answer Technique:
- Set low and high bounds for possible answers.
- Calculate mid = (low + high) // 2.
- Check if mid is valid.
- If valid, move high to mid.
- If not valid, move low to mid + 1.
- Repeat until low == high; low is the answer.

Full Transcript

Binary Search on Answer Technique helps find the smallest or largest value that satisfies a condition. We start with a range (low to high). We pick the middle value (mid) and check if it meets the condition. If it does, we try smaller values by moving high to mid. If it doesn't, we try bigger values by moving low to mid plus one. We repeat this until low and high meet. That point is our answer. The example shows this process step by step, updating low and high based on validity checks until the answer is found.

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