Binary Search on Answer Technique in DSA Javascript - 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 of possible answers, check the middle value, adjust range based on validity, repeat until the answer is found.

Execution Sample

DSA Javascript

function binarySearchAnswer(low, high, isValid) {
  while (low < high) {
    let mid = Math.floor((low + high) / 2);
    if (isValid(mid)) high = mid;
    else low = mid + 1;
  }
  return low;
}

This code finds the smallest valid answer between low and high using binary search on the answer space.

Execution Table

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

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
low	1	6	6	6	7	7	7
high	10	10	8	7	7	7	7
mid	-	5	8	7	6	-	-
isValid(mid)	-	false	true	true	false	-	-

Key Moments - 3 Insights

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

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

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

Because mid might be the smallest valid answer, so we keep it by setting high = mid. This happens in steps 3 and 4.

Why does the loop stop when low equals high?

Because the search space is narrowed down to one value, which is the smallest valid answer, as seen in step 6.

Visual Quiz - 3 Questions

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

A 8

B 7

C 6

D 5

💡 Hint

Check the 'mid' column in row with Step 4 in the execution_table.

At which step does 'low' first become 7?

A Step 5

B Step 3

C Step 2

D Step 6

💡 Hint

Look at the 'low' values in variable_tracker after each step.

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

A 10

B 6

C 5

D 1

💡 Hint

When isValid(mid) is true, high is set to mid, see steps 3 and 4 for reference.

Concept Snapshot

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

Full Transcript

Binary Search on Answer Technique starts by setting a range of possible answers with low and high. We find the middle value mid and check if it is a valid answer using a condition function. If mid is valid, we move the high bound down to mid to keep searching for a smaller valid answer. If mid is not valid, we move the low bound up to mid plus one to discard invalid answers. This process repeats until low equals high, which is the smallest valid answer. The code example shows this logic in a loop, updating low and high based on validity checks. The execution table traces each step, showing how low, high, and mid change, and when the loop stops. Key moments clarify why we update low or high in certain ways and why the loop ends when low equals high. The visual quiz tests understanding of mid values, variable updates, and the effect of validity checks. This technique is useful for problems where the answer lies within a range and can be checked for validity efficiently.

Practice

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

easy

A. We guess an answer and use binary search to find the smallest or largest valid value.

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

C. We use binary search to find the middle element in a sorted list.

D. We apply binary search to split the array into two halves repeatedly.

Solution

1. Step 1: Understand the technique's goal

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

2. Step 2: Use binary search on the answer range

   We narrow down the answer by checking mid-values until we find the smallest or largest valid answer.

3. Final Answer:

   We guess an answer and use binary search to find the smallest or largest valid value. -> Option A

4. Quick Check:

   Binary Search on Answer = Guess and check with binary search [OK]

Hint: Think of binary searching the answer, not the array [OK]

Common Mistakes:

• Confusing it with normal binary search on sorted arrays
• Trying to binary search elements instead of answer values
• Not defining a valid check function for guesses

2. Which of the following is the correct syntax to start a binary search on answer in JavaScript for a range from low to high?

easy

A. for (let mid = low; mid <= high; mid++) { }

B. while (low <= high) { let mid = Math.floor((low + high) / 2); }

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

D. do { mid = (low + high) / 2; } while (low < high);

Solution

1. Step 1: Identify the binary search loop structure

   Binary search uses a while loop checking low <= high to continue searching.

2. Step 2: Calculate mid correctly

   Mid is calculated as Math.floor((low + high) / 2) to get the middle integer index.

3. Final Answer:

   while (low <= high) { let mid = Math.floor((low + high) / 2); } -> Option B

4. Quick Check:

   Correct binary search loop syntax = while (low <= high) { let mid = Math.floor((low + high) / 2); } [OK]

Hint: Use while loop with low <= high and floor mid [OK]

Common Mistakes:

• Using for loop instead of while for binary search
• Not flooring mid value causing float indices
• Using incorrect loop conditions like low < high

3. Consider the following code snippet using binary search on answer to find the minimum capacity to ship packages within D days:

function canShip(weights, capacity, D) {
  let days = 1, currentLoad = 0;
  for (let w of weights) {
    if (currentLoad + w > capacity) {
      days++;
      currentLoad = 0;
    }
    currentLoad += w;
  }
  return days <= D;
}

function shipWithinDays(weights, D) {
  let low = Math.max(...weights);
  let high = weights.reduce((a, b) => a + b, 0);
  while (low < high) {
    let mid = Math.floor((low + high) / 2);
    if (canShip(weights, mid, D)) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  return low;
}

console.log(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5));

What is the output of this code?

medium

A. 20

B. 10

C. 15

D. 5

Solution

1. Step 1: Understand the problem and code

   The code finds the minimum ship capacity to ship weights in 5 days. It uses binary search between max weight (10) and sum (55).

2. Step 2: Trace binary search narrowing

   Checking mid values, the minimum capacity that allows shipping in 5 days is 15.

3. Final Answer:

   15 -> Option C

4. Quick Check:

   Minimum capacity to ship in 5 days = 15 [OK]

Hint: Check max weight and sum, binary search between them [OK]

Common Mistakes:

• Choosing max weight (10) as answer instead of minimum capacity
• Choosing total sum (55) instead of minimum valid capacity
• Misunderstanding the days condition in canShip

4. The following code tries to find the maximum length of a rope to cut at least k pieces using binary search on answer. Find the bug:

function maxLength(ropes, k) {
  let low = 0;
  let high = Math.max(...ropes);
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    let count = 0;
    for (let r of ropes) {
      count += Math.floor(r / mid);
    }
    if (count >= k) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return high;
}

medium

A. Using while (low <= high) instead of while (low < high) is wrong.

B. Not sorting ropes before binary search causes wrong answer.

C. Returning high instead of low is incorrect.

D. Starting low from 0 causes division by zero error.

Solution

1. Step 1: Identify potential division by zero

   Starting low at 0 means mid can be 0, causing division by zero in Math.floor(r / mid).

2. Step 2: Fix low initialization

   Set low to 1 to avoid division by zero and ensure valid rope length guesses.

3. Final Answer:

   Starting low from 0 causes division by zero error. -> Option D

4. Quick Check:

   low = 0 causes divide by zero [OK]

Hint: Avoid zero as divisor in binary search on answer [OK]

Common Mistakes:

• Ignoring division by zero possibility
• Changing loop condition unnecessarily
• Returning wrong boundary without reason

5. You want to find the minimum maximum time to complete all tasks by k workers, where each worker can do consecutive tasks only. Given task times array tasks, how would you apply binary search on answer to solve this?

Choose the best approach:

hard

A. Binary search on time range; check if tasks can be split into ≤ k groups with max sum ≤ mid.

B. Sort tasks and binary search for the smallest task time.

C. Use binary search on number of tasks each worker gets, ignoring task times.

D. Apply binary search on total tasks count to assign tasks evenly.

Solution

1. Step 1: Define the answer range

   The minimum max time is at least max task time, max is sum of all tasks.

2. Step 2: Check feasibility with mid value

   Check if tasks can be split into ≤ k groups where each group's sum ≤ mid.

3. Step 3: Use binary search to narrow answer

   Adjust low and high based on feasibility until minimum max time is found.

4. Final Answer:

   Binary search on time range; check if tasks can be split into ≤ k groups with max sum ≤ mid. -> Option A

5. Quick Check:

   Binary search on max time with group feasibility check [OK]

Hint: Binary search answer range, check group splits feasibility [OK]

Common Mistakes:

• Binary searching on tasks count instead of time
• Ignoring consecutive task grouping constraint
• Sorting tasks unnecessarily