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.