Binary Search on Answer Technique in DSA Typescript - Time & Space Complexity

Time Complexity: Binary Search on Answer Technique

O(log n)

Understanding Time Complexity

We want to understand how fast the binary search on answer technique finds the best solution.

How does the number of steps grow as the range of possible answers grows?

Scenario Under Consideration

Analyze the time complexity of this binary search on answer code.

function binarySearchOnAnswer(low: number, high: number, check: (mid: number) => boolean): number {
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (check(mid)) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return low;
}
    

This code tries to find the smallest value that passes the check by narrowing the search range.

Identify Repeating Operations

Look for loops or repeated steps.

• Primary operation: The while loop that halves the search range each time.
• How many times: About log base 2 of the size of the range (high - low + 1).

How Execution Grows With Input

Each step cuts the search space in half, so the number of steps grows slowly.

Input Size (range size)	Approx. Operations (loop iterations)
10	About 4
100	About 7
1000	About 10

Pattern observation: Doubling the input size adds only one more step.

Final Time Complexity

Time Complexity: O(log n)

This means the steps grow slowly, making it efficient even for large ranges.

Common Mistake

[X] Wrong: "The loop runs once for every number in the range, so it is O(n)."

[OK] Correct: Each loop cuts the range in half, so the number of loops grows much slower than the range size.

Interview Connect

Understanding this technique shows you can solve problems efficiently by smart searching, a skill valued in many coding challenges.

Self-Check

What if the check function took longer to run? How would that affect the overall time complexity?