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

Time Complexity: Binary Search on Answer Technique

O(log n)

Understanding Time Complexity

We want to understand how the time taken by the binary search on answer technique changes as the input size grows.

Specifically, how many steps does it take to find the correct answer by narrowing down the search space?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code tries to find the smallest value that satisfies a condition by repeatedly checking the middle value and narrowing the search range.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that halves the search range each time.
• How many times: The loop runs until the search range is empty, roughly halving the range each step.

How Execution Grows With Input

Each step cuts the search space in half, so the number of steps grows slowly even if the input range grows a lot.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the input size adds only one extra step, showing very slow growth.

Final Time Complexity

Time Complexity: O(log n)

This means the number of steps grows slowly, increasing by one step each time the input size doubles.

Common Mistake

[X] Wrong: "The loop runs n times because it checks every number between low and high."

[OK] Correct: The loop does not check every number; it halves the search space each time, so it runs much fewer times than n.

Interview Connect

Understanding this technique shows you can efficiently find answers in large search spaces by smartly narrowing down options, a valuable skill in problem solving.

Self-Check

"What if the condition function takes linear time to check each mid? How would that affect the overall time complexity?"