Binary Search on Answer Technique in DSA Typescript

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 trying to find the right temperature to bake a cake by guessing a temperature, baking, and checking if it's done. If it's undercooked, increase the temperature; if burnt, decrease it.

low -> [mid] -> high
  ↑       ↑       ↑
 guess   check   limit

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5, 6, 7, 8, 9], goal: find smallest number x such that x*x >= 20

Goal: Find the smallest number whose square is at least 20 using binary search on answer

Step 1: Set low=1, high=9, mid=(1+9)//2=5, check 5*5=25 >= 20

low=1 -> mid=5 -> high=9
Check: 25 >= 20 is true

Why: Check if mid squared meets condition to decide search direction

Step 2: Since 25 >= 20, set high=mid=5 to search smaller or equal values

low=1 -> mid=? -> high=5

Why: Try to find smaller number that still satisfies condition

Step 3: Calculate mid=(1+5)//2=3, check 3*3=9 < 20

low=1 -> mid=3 -> high=5
Check: 9 < 20 is true

Why: Mid too small, need to increase low

Step 4: Since 9 < 20, set low=mid+1=4

low=4 -> mid=? -> high=5

Why: Discard values less than mid+1

Step 5: Calculate mid=(4+5)//2=4, check 4*4=16 < 20

low=4 -> mid=4 -> high=5
Check: 16 < 20 is true

Why: Mid still too small, increase low

Step 6: Since 16 < 20, set low=mid+1=5

low=5 -> mid=? -> high=5

Why: Narrow down to high

Step 7: Calculate mid=(5+5)//2=5, check 5*5=25 >= 20

low=5 -> mid=5 -> high=5
Check: 25 >= 20 is true

Why: Found candidate, try smaller or equal

Step 8: Since 25 >= 20, set high=mid=5

low=5 -> high=5

Why: Search ends when low == high

Result:

low=5 -> 5*5=25 >= 20
Answer: 5

Annotated Code

DSA Typescript

class BinarySearchOnAnswer {
  static smallestNumberSatisfyingCondition(low: number, high: number, condition: (x: number) => boolean): number {
    while (low < high) {
      const mid = Math.floor((low + high) / 2);
      if (condition(mid)) {
        high = mid; // try smaller or equal values
      } else {
        low = mid + 1; // increase low to discard mid
      }
    }
    return low;
  }
}

// Driver code
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
const condition = (x: number) => x * x >= 20;
const result = BinarySearchOnAnswer.smallestNumberSatisfyingCondition(1, 9, condition);
console.log(result + "");

while (low < high) {

loop until search space narrows to one value

const mid = Math.floor((low + high) / 2);

calculate middle guess

if (condition(mid)) {

check if mid satisfies condition

high = mid; // try smaller or equal values

narrow search to left half including mid

else { low = mid + 1; }

discard mid and left half, search right half

return low;

return smallest value satisfying condition

Output

5

Complexity Analysis

Time: O(log n) because each step halves the search space between low and high

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), binary search on answer is much faster for large ranges

Edge Cases

low equals high at start

Returns low immediately as answer

DSA Typescript

while (low < high) {

no value satisfies condition

Returns high + 1 or out of range; user must ensure condition is valid

DSA Typescript

return low;

condition true for all values

Returns low as smallest satisfying value

DSA Typescript

if (condition(mid)) {

When to Use This Pattern

When you need to find a numeric answer that meets a yes/no condition and the answer space is sorted or monotonic, use binary search on answer to efficiently find it.

Common Mistakes

Mistake: Updating low to mid instead of mid + 1 when condition is false causes infinite loop
Fix: Set low = mid + 1 to ensure progress

Mistake: Not handling the case when low == high causes extra unnecessary iterations
Fix: Use while (low < high) loop condition

Summary

Finds the smallest or largest value that satisfies a condition by guessing and checking.

Use when the answer space is numeric and the condition is monotonic (always true or false beyond a point).

The key insight is to treat the answer as a search space and narrow it down using binary search.

Practice

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

easy

A. We guess an answer and check if it satisfies the problem constraints, then adjust the guess.

B. We sort the input array before applying binary search.

C. We use binary search only on sorted arrays to find elements.

D. We divide the input into two halves and solve each recursively.

Solution

1. Step 1: Understand the technique's purpose

   Binary Search on Answer guesses a possible answer value 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 values accordingly to find the optimal answer.

3. Final Answer:

   We guess an answer and check if it satisfies the problem constraints, then adjust the guess. -> Option A

4. Quick Check:

   Guess and check approach = C [OK]

Hint: Think of guessing answers and verifying them stepwise [OK]

Common Mistakes:

• Confusing with normal binary search on arrays
• Assuming input must be sorted
• Thinking it divides input recursively

2. Which of the following is the correct TypeScript syntax to start a binary search on answer between low and high?

easy

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

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

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

D. if (low < high) { let mid = (low + high) >> 1; }

Solution

1. Step 1: Identify correct mid calculation

   Midpoint must be an integer index, so use Math.floor to avoid decimals.

2. Step 2: Confirm loop condition and syntax

   Use while loop with condition low <= high for binary search iteration.

3. Final Answer:

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

4. Quick Check:

   Integer mid with while loop = B [OK]

Hint: Use Math.floor for mid to avoid decimals in binary search [OK]

Common Mistakes:

• Using division without floor causing float mid
• Using for loop instead of while
• Using bitwise shift without understanding

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

function canShip(weights: number[], capacity: number, D: number): boolean {
  let days = 1, total = 0;
  for (const w of weights) {
    if (total + w > capacity) {
      days++;
      total = 0;
    }
    total += w;
  }
  return days <= D;
}

function shipWithinDays(weights: number[], D: number): number {
  let low = Math.max(...weights);
  let high = weights.reduce((a, b) => a + b, 0);
  while (low < high) {
    const 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?

medium

A. 15

B. 10

C. 20

D. 5

Solution

1. Step 1: Understand problem and code

   We find minimum ship capacity to ship weights in 5 days. Minimum capacity is max weight (10), max capacity is sum (55).

2. Step 2: Trace binary search and canShip checks

   Binary search narrows capacity to 15, which allows shipping in 5 days by grouping weights properly.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Minimum capacity = 15 [OK]

Hint: Check max weight as low and sum as high for binary search [OK]

Common Mistakes:

• Choosing max weight instead of sum as answer
• Confusing days count in canShip function
• Not using Math.floor for mid calculation

4. The following TypeScript code tries to find the maximum minimum distance between elements placed in positions array using binary search on answer. Identify the bug:

function canPlace(positions: number[], distance: number, m: number): boolean {
  let count = 1, lastPos = positions[0];
  for (let i = 1; i < positions.length; i++) {
    if (positions[i] - lastPos >= distance) {
      count++;
      lastPos = positions[i];
    }
  }
  return count >= m;
}

function maxMinDistance(positions: number[], m: number): number {
  positions.sort((a, b) => a - b);
  let low = 0, high = positions[positions.length - 1] - positions[0];
  while (low < high) {
    const mid = Math.floor((low + high + 1) / 2);
    if (canPlace(positions, mid, m)) low = mid;
    else high = mid - 1;
  }
  return low;
}

medium

A. Missing increment of count inside canPlace

B. Binary search mid calculation should not add 1

C. Binary search loop condition should be low <= high

D. No bug; code works correctly

Solution

1. Step 1: Analyze canPlace function

   It correctly counts placements with given minimum distance.

2. Step 2: Check binary search logic

   Mid uses upper mid to avoid infinite loop, loop condition low < high is valid, and updates low/high correctly.

3. Final Answer:

   No bug; code works correctly -> Option D

4. Quick Check:

   Code logic correct = A [OK]

Hint: Use upper mid to avoid infinite loop in binary search [OK]

Common Mistakes:

• Changing loop condition incorrectly
• Removing +1 in mid causing infinite loop
• Forgetting to sort positions array

5. You want to find the minimum maximum time to complete all tasks by k workers, where each worker does continuous tasks. Given tasks array of times, how would you apply binary search on answer to solve this?
Choose the best approach.

hard

A. Calculate average time and assign tasks evenly without binary search.

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

C. Use binary search on number of tasks per worker directly.

D. Sort tasks and assign largest tasks first to workers.

Solution

1. Step 1: Define search space for answer

   Minimum max time is max single task time; maximum is sum of all tasks.

2. Step 2: Check feasibility with mid value

   Check if tasks can be divided into ≤ k continuous groups with max sum ≤ mid.

3. Step 3: Adjust search space based on feasibility

   If feasible, try smaller max time; else increase it.

4. Final Answer:

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

5. Quick Check:

   Binary search on max time with group check = D [OK]

Hint: Binary search answer space, check feasibility with grouping [OK]

Common Mistakes:

• Sorting tasks instead of binary searching answer
• Trying to binary search on task count directly
• Ignoring continuous group constraint