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

Time Complexity: Binary Search Iterative Approach

O(log n)

Understanding Time Complexity

We want to understand how the time taken by binary search changes as the list 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): number {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}
    

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: 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 area in half, so the number of steps grows slowly as the list gets bigger.

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

Pattern observation: Doubling the input size adds only one more step to the search.

Final Time Complexity

Time Complexity: O(log n)

This means the search steps grow slowly, adding just one step each time the list size doubles.

Common Mistake

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

[OK] Correct: Binary search skips half the list each step, so it does not check every element, making it much faster than linear search.

Interview Connect

Understanding binary search time complexity shows you can analyze efficient algorithms, a key skill in problem solving and coding interviews.

Self-Check

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