Binary Search on Answer Technique in DSA C++ - 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 correct answer.

How does the number of steps grow when the search range gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int binarySearchOnAnswer(int low, int high) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(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 of the current 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: About log₂ of the size of the search range.

How Execution Grows With Input

Each step cuts the search range roughly in half, so the number of steps grows slowly as the range grows.

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.

Final Time Complexity

Time Complexity: O(log n)

This means the number of steps grows slowly, making the search very efficient even for large ranges.

Common Mistake

[X] Wrong: "The binary search on answer takes linear time because it checks many values."

[OK] Correct: It does not check every value; it smartly halves the search range each time, reducing steps drastically.

Interview Connect

Understanding this technique shows you can solve problems efficiently by narrowing down answers quickly, a skill valued in many coding challenges.

Self-Check

"What if the check function takes linear time itself? How would that affect the overall time complexity?"