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

Time Complexity: Find Peak Element Using Binary Search

O(log n)

Understanding Time Complexity

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

func findPeakElement(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        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 index by repeatedly narrowing the search range using binary search.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for loop that halves the search range each time.
• How many times: The loop runs until the search range is one element, about log base 2 of n times.

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

Common Mistake

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

[OK] Correct: The loop does not check every element; it cuts the search space in half each time, so it runs much fewer times.

Interview Connect

Understanding this time complexity shows you can use efficient search methods, a key skill in many coding challenges and real-world problems.

Self-Check

"What if we changed the array to be unsorted without any peak guarantee? How would the time complexity change?"