Binary Search as Divide and Conquer in DSA Typescript - Time & Space Complexity

Time Complexity: Binary Search as Divide and Conquer

O(log n)

Understanding Time Complexity

We want to understand how fast 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.

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 looks for a target number in a sorted list by repeatedly cutting the search area in half.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking the middle element and adjusting the search range.
• How many times: The search range halves each time until the target is found or range is empty.

How Execution Grows With Input

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

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

Pattern observation: Doubling the list size adds only one more check.

Final Time Complexity

Time Complexity: O(log n)

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

Common Mistake

[X] Wrong: "Binary search checks every element one by one like a simple search."

[OK] Correct: Binary search skips half the list each time, so it does far fewer checks than looking at every element.

Interview Connect

Understanding binary search time helps you explain how to quickly find items in sorted data, a key skill in many coding tasks.

Self-Check

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