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

Time Complexity: Binary Search on Answer Technique

O(log n)

Understanding Time Complexity

We want to understand how the time needed grows when using the binary search on answer method.

This helps us know how fast the solution finds the correct answer by narrowing down possibilities.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func binarySearchOnAnswer(low, high int, condition func(int) bool) int {
    for low <= high {
        mid := (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 of a range.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The loop that halves the search range each time.
• How many times: The loop runs about log base 2 of the range size times.

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(log n)

This means the time needed grows slowly, increasing by one step each time the input doubles.

Common Mistake

[X] Wrong: "The loop runs n times because it looks like a while loop over a range."

[OK] Correct: Each loop cuts the range in half, so it runs much fewer times than n, about log n times.

Interview Connect

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

Self-Check

"What if the condition function takes linear time to check? How would the overall time complexity change?"