Binary Search Recursive Approach in DSA Go - Time & Space Complexity

Time Complexity: Binary Search Recursive Approach

O(log n)

Understanding Time Complexity

We want to understand how fast the recursive binary search finds a number in a sorted list.

How does the time it takes change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func binarySearch(arr []int, target, low, high int) int {
    if low > high {
        return -1
    }
    mid := low + (high - low) / 2
    if arr[mid] == target {
        return mid
    } else if arr[mid] > target {
        return binarySearch(arr, target, low, mid-1)
    } else {
        return binarySearch(arr, target, mid+1, high)
    }
}

This code searches for a target number in a sorted list by repeatedly dividing the search range in half.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive call that halves the search range each time.
• How many times: The search range is halved each call, repeating until the range is empty or target found.

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(log n)

This means the search time grows slowly, adding just a few more steps even if the list gets much bigger.

Common Mistake

[X] Wrong: "Binary search checks every item one by one, so it takes as long as the list size."

[OK] Correct: Binary search skips half the list each time, so it does not check every item, making it much faster.

Interview Connect

Understanding binary search time helps you explain efficient searching clearly and confidently in interviews.

Self-Check

"What if the list was not sorted? How would the time complexity of searching change?"