Binary Search on Answer Technique in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Binary Search on Answer Technique?

It is a method to find an unknown value by guessing an answer range and using binary search to narrow down the correct answer based on a condition check.

beginner

In Binary Search on Answer, what do we usually need besides the search range?

A function or condition that tells if a guessed answer is valid or not, helping us decide to search higher or lower.

intermediate

Why is Binary Search on Answer useful for optimization problems?

Because it efficiently finds the best possible answer by checking feasibility instead of trying all possibilities, saving time.

beginner

What is a typical step in implementing Binary Search on Answer?

Set low and high bounds, then repeatedly check the middle value with a condition until low meets high.

intermediate

Give an example problem where Binary Search on Answer can be applied.

Finding the minimum maximum load to divide tasks among workers so that no worker has to do more than that load.

What does the 'answer' represent in Binary Search on Answer?

A The number of iterations in binary search

B The index of an element in an array

C The size of the input data

D A guessed value within a range to test feasibility

The 'answer' is a value we guess and test if it meets the problem's condition.

Which of these is NOT required for Binary Search on Answer?

A Low and high bounds for binary search

B A search range for the answer

C A sorted array

D A condition function to check guesses

Binary Search on Answer does not require a sorted array, only a range and a condition.

If the condition function returns false for a guess, what should you do?

A Search in the higher half

B Search in the lower half

C Stop the search

D Return the guess immediately

If the guess is not valid, we try bigger values by searching the higher half.

What is the time complexity of Binary Search on Answer if the condition check is O(n)?

A O(n log m), where m is the search range size

B O(log n)

C O(n^2)

D O(m)

Binary search runs in log m steps, each with an O(n) condition check, total O(n log m).

Which problem type is a good fit for Binary Search on Answer?

A Finding an element in a sorted list

B Finding the minimum feasible value that satisfies a condition

C Sorting an array

D Calculating factorial

Binary Search on Answer finds the smallest or largest value meeting a condition.

Explain how Binary Search on Answer works and why it is useful.

Think about how you guess and check answers instead of trying all.

Describe a real-life example where Binary Search on Answer could help solve a problem.

Consider dividing tasks or resources fairly.

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