162. Find Peak Element

The Find Peak Element problem is a classic introduction to using binary search beyond sorted arrays. It’s a favorite in interviews because it demonstrates how a simple neighbor check can reveal which half of the current search window must contain a peak while meeting the strict O(logn)O(log n)O(logn) requirement.

Problem statement

You’re given an integer array nums where adjacent values are guaranteed to be different. A peak is an index i such that nums[i] is strictly greater than its immediate neighbors (treat values outside the array as negative infinity). Your task is to find and return the index of any peak.

This is trickier than it first appears because there can be multiple peaks, and a straightforward scan is insufficient when you’re required to complete in logarithmic time.

Constraints:

• 1 ≤ nums.length ≤ 1000
• −2³¹ ≤ nums[i] ≤ 2³¹−1
• nums[i] != nums[i + 1] for all valid i.

Examples

Naive approach

A straightforward approach is to check each index and see whether it’s greater than its neighbors. That works, but it takes linear time $O(n)$ because you may examine every element. Since the problem requires a logarithmic-time solution, scanning the full array is not acceptable.

Optimal solution using Binary Search

To improve upon the linear time complexity of a straightforward scan, we need a different approach to determine where a peak must exist. Instead of checking every index, we take advantage of the fact that adjacent elements are different, so between any two neighbors, the array is always either going up or down. That provides us with a reliable signal at any index, indicating which side can still contain a valid peak, thereby allowing us to quickly shrink the search space.

The core idea is to use binary search using a quick comparison between adjacent elements. At a midpoint mid, we compare nums[mid] with its immediate element to the right, i.e., nums[mid+1] to see which direction the array is moving at that spot. If this element is less than the element to the right, the array is going up from mid to mid + 1, which means we’re heading toward higher values—so a peak must exist somewhere in the right half (mid + 1 .. right). Otherwise (nums[mid] > nums[mid + 1]), the array goes down from mid to mid + 1, so a peak must be on the left half (left .. mid), possibly at mid itself. Repeating this decision keeps halving the range until only one index remains, which is necessarily a peak, giving us an O(log n) solution without scanning the entire array.

Algorithmic Steps

This algorithm is implemented as follows:

1. Initialize two variables: left = 0 and right = len(nums) - 1.
2. While left is less than right:
   1. Compute the middle index mid by taking the floor of the average of left and right.
   2. If nums[mid] < nums[mid + 1],
      1. Set left to mid + 1.
   3. Otherwise,
      1. Set right to mid.
3. When the loop ends, return left (which equals right) as a peak index.

To better understand the solution, let’s walk through the algorithm using the illustration below:

1 / 6

Executable Python implementation

The code below implements the algorithm described above.

def findPeakElement(nums) : 
    """ Binary search on slope: 
        - If nums[mid] < nums[mid+1], peak must be on the right.
        - Else, peak must be on the left (including mid).
    """
    # Search boundaries: we will shrink [left, right] until they meet at a peak index
    left, right = 0, len(nums) - 1

    # Loop until the search space narrows down to one index
    while left < right:
        # Midpoint of the current range
        mid = (left + right) // 2

        # Compare mid with its right neighbor to determine the slope direction
        if nums[mid] < nums[mid + 1]:
            # Uphill: peak is guaranteed to be in the right half (excluding mid)
            left = mid + 1
        else:
            # Downhill or peak at mid: peak is guaranteed to be in the left half (including mid)
            right = mid

    # When left == right, we've converged to a peak index
    return left

# Driver code
def main():
    test_cases = [
        [10, 9, 2, 5, 3, 7, 101, 18],
        [0, 1, 0, 3, 2, 3],
        [7, 7, 7, 7, 7],
        [5, 4, 3, 2, 1],
        [1, 3, 6, 7, 9, 4, 10, 5, 6]]

    for i, nums in enumerate(test_cases, 1):
        result = findPeakElement(nums)
        print(f"Test Case {i}:")
        print(f"\tInput: {nums}")
        print(f"\tOutput: {result}")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time complexity

The time complexity of this solution is O(log⁡n) because each loop iteration discards roughly half of the remaining search interval, and the loop continues until the interval collapses to a single index.

Space complexity

The space complexity is O(1)) because the algorithm uses only a constant amount of extra memory (a few pointers), regardless of the input size.

Common pitfalls to avoid

• Using mid - 1 and mid + 1 checks everywhere and going out of bounds: This solution avoids that by only comparing nums[mid] with nums[mid + 1], which is safe as long as mid < right.
• Writing right = mid - 1 in the decreasing-slope case: That can skip over a valid peak at mid. The correct move is right = mid because mid itself may be the peak.
• Assuming the array is “mountain-shaped”: The array can have multiple rises and falls. The slope-based binary search still works because it only needs a local slope direction to guarantee a peak exists in that half.
• Trying to compare both neighbors always: You don’t need to check mid-1 explicitly; comparing mid with mid+1 is enough to decide which side must contain a peak.