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

Time Complexity: Binary Search Recursive Approach

O(log n)

Understanding Time Complexity

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

Specifically, how many steps does it take to find a number in a sorted list?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function binarySearch(arr: number[], target: number, left: number, right: number): number {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  else if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  else return binarySearch(arr, target, mid + 1, right);
}
    

This code searches for a target number in a sorted array 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: At most, the function calls itself until the search range is empty, roughly halving the size each time.

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(log n)

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

Common Mistake

[X] Wrong: "Binary search checks every element one by one, so it is O(n)."

[OK] Correct: Binary search does not check all elements; it cuts the search area in half each time, so it only needs about log n steps.

Interview Connect

Understanding binary search's time complexity shows you can analyze efficient algorithms, a key skill in coding interviews and real projects.

Self-Check

What if we changed the array to be unsorted? How would the time complexity of searching change?