Find Peak Element Using Binary Search in DSA Javascript - 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 change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findPeakElement(nums) {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    let 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 narrowing the search range using binary search.

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: About log base 2 of the input size times (because the range halves each step).

How Execution Grows With Input

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

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 steps needed grow slowly, making the search very efficient even for large arrays.

Common Mistake

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

[OK] Correct: The search range halves each time, so the loop runs much fewer times than the number of elements.

Interview Connect

Understanding how binary search reduces work quickly is a key skill that shows you can write fast and smart code.

Self-Check

"What if we changed the array to be sorted and wanted to find a specific value instead of a peak? How would the time complexity change?"