Find Peak Element Using Binary Search in DSA C++ - 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.

int findPeakElement(std::vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

This code finds a peak element by repeatedly dividing 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 halves the search range each time.
• How many times: About log base 2 of n times, where n is the array size.

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 steps needed grow very slowly even if the array gets much bigger.

Common Mistake

[X] Wrong: "The loop runs n times because it looks like it checks each element."

[OK] Correct: Actually, the loop cuts the search space in half each time, so it runs much fewer times than n.

Interview Connect

Understanding this binary search approach shows you can find answers quickly by smartly reducing work, a key skill in many coding challenges.

Self-Check

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