Find Peak Element in O(log n) Time Complexity using C++

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1, 2, 3, 1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1, 2, 1, 3, 5, 6, 4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your algorithm should run in O(log n) time and use O(1) extra space.

Understanding the Problem

The core challenge of this problem is to find an element in the array that is greater than its neighbors. This is significant in various applications such as finding local maxima in signal processing or identifying peaks in data analysis. A common pitfall is assuming that the peak must be the global maximum, but any local peak is sufficient.

Approach

To solve this problem efficiently, we can use a binary search approach. A naive solution would involve scanning the array linearly, which would take O(n) time. However, the problem constraints require an O(log n) solution, which suggests a binary search method.

Naive Solution

The naive approach involves iterating through the array and checking each element to see if it is greater than its neighbors. This approach is straightforward but not optimal:

// Naive approach
int findPeakElement(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        if ((i == 0 || nums[i] > nums[i - 1]) && (i == nums.size() - 1 || nums[i] > nums[i + 1])) {
            return i;
        }
    }
    return -1;
}

This approach has a time complexity of O(n), which is not efficient for large arrays.

Optimized Solution

The optimized solution uses a binary search approach. The idea is to divide the array into two halves and determine which half contains a peak element. This is based on the observation that if an element is not a peak and it is greater than its left neighbor, then there must be a peak element on the right half, and vice versa.

Algorithm

Here is a step-by-step breakdown of the binary search algorithm:

Initialize two pointers, left and right, to the start and end of the array.
While left is less than right:
- Calculate the middle index mid.
- If nums[mid] is greater than nums[mid + 1], then the peak is in the left half, so set right to mid.
- Otherwise, the peak is in the right half, so set left to mid + 1.
When left equals right, the peak element is found, and left (or right) is the index of the peak element.

Code Implementation

#include <vector>
using namespace std;

// Optimized binary search approach
int findPeakElement(vector<int>& nums) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        
        // Check if mid element is greater than the next element
        if (nums[mid] > nums[mid + 1]) {
            // Peak is in the left half
            right = mid;
        } else {
            // Peak is in the right half
            left = mid + 1;
        }
    }
    
    // left and right converge to the peak element
    return left;
}

Complexity Analysis

The time complexity of the binary search approach is O(log n) because we are halving the search space in each iteration. The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Consider the following edge cases:

Array with a single element: The single element is the peak.
Array with all elements in increasing or decreasing order: The peak will be the last or first element, respectively.

These cases are handled naturally by the binary search algorithm.

Testing

To test the solution comprehensively, consider the following test cases:

Single element array: [1]
All elements in increasing order: [1, 2, 3, 4, 5]
All elements in decreasing order: [5, 4, 3, 2, 1]
Array with multiple peaks: [1, 3, 2, 4, 1]

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem constraints and requirements.
Think about different approaches and their time complexities.
Use binary search for problems that require O(log n) solutions.
Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to find a peak element in an array using a binary search approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving algorithmic thinking and problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: