Binary Search on Answer Technique in DSA C# - Execution Trace

Concept Flow - Binary Search on Answer Technique

Set low = min possible answer

↓

Set high = max possible 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 of possible answers, check the middle, then narrow the range based on validity until the answer is found.

Execution Sample

DSA C#

int low = 1;
int high = 10;
while (low < high) {
  int mid = (low + high) / 2;
  if (IsValid(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	low	high	mid	IsValid(mid)?	Action	Range After Action
1	1	10	5	No	low = mid + 1	[6, 10]
2	6	10	8	Yes	high = mid	[6, 8]
3	6	8	7	Yes	high = mid	[6, 7]
4	6	7	6	No	low = mid + 1	[7, 7]
5	7	7	-	-	Exit loop	[7, 7]

💡 Loop ends when low equals high, low is the smallest valid answer.

Variable Tracker

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

Key Moments - 3 Insights

Why do we update 'high = mid' when mid is valid instead of 'high = mid - 1'?

Because mid itself can be the smallest valid answer, so we keep it in the range. See Step 2 and 3 in execution_table where high is set to mid.

Why does the loop stop when low equals high?

Because the search range has narrowed to a single number, which is the smallest valid answer. Step 5 shows low and high both at 7.

Why do we set 'low = mid + 1' when mid is not valid?

Because mid is too small or invalid, so the answer must be greater than mid. Step 1 and 4 show low updated to mid + 1.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at Step 3?

A 6

B 7

C 8

D 5

💡 Hint

Check the 'mid' column in the execution_table row for Step 3.

At which step does the condition 'IsValid(mid)?' return Yes for the first time?

A Step 4

B Step 1

C Step 2

D Step 3

💡 Hint

Look at the 'IsValid(mid)?' column in execution_table to find the first 'Yes'.

If 'IsValid(mid)' was always No, what would happen to 'low' in the execution_table?

A It would increase until it equals high

B It would decrease

C It would stay the same

D It would become negative

💡 Hint

See how 'low' changes when 'IsValid(mid)?' is No in the variable_tracker.

Concept Snapshot

Binary Search on Answer Technique:
- Define low and high as answer range
- Calculate mid = (low + high) / 2
- Check if mid is valid
- If valid, set high = mid (keep mid)
- Else, set low = mid + 1 (exclude mid)
- Repeat until low == high
- low is the smallest valid answer

Full Transcript

Binary Search on Answer Technique starts by setting a range low to high for possible answers. We find the middle value mid and check if it is valid. If mid is valid, we keep it by moving high to mid. If not valid, we move low to mid plus one. We repeat this until low equals high, which is the smallest valid answer. The execution table shows step by step how low, high, and mid change, and how the range narrows. Key points include why we keep mid when valid and why the loop stops when low equals high.

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