Find Peak Element Using Binary Search in DSA Typescript - Time & Space Complexity

Time Complexity: Find Peak Element Using Binary Search

O(log n)

Understanding Time Complexity

We want to know how fast the binary search method finds a peak element in an array.

How does the number of steps grow as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findPeakElement(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[mid + 1]) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}
    

This code finds a peak element by repeatedly cutting the search space in half using binary search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that compares middle elements and moves left or right pointers.
• How many times: The loop runs until the search space is reduced to one element, roughly halving each time.

How Execution Grows With Input

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

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

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

Final Time Complexity

Time Complexity: O(log n)

This means the time to find a peak grows very slowly even if the array gets much bigger.

Common Mistake

[X] Wrong: "The loop runs once for every element, so it is O(n)."

[OK] Correct: Each step cuts the search space in half, so the number of steps grows with the logarithm of the input size, not linearly.

Interview Connect

Understanding this binary search approach shows you can use smart searching to save time, a skill valued in many coding challenges.

Self-Check

What if we changed the array to be sorted strictly increasing or decreasing? How would the time complexity change?