Finding a Peak Element in an Array with Binary Search

When working with arrays, a common problem is finding a peak element. A peak element is defined as an element that is greater than its neighbors. Given an array, the goal is to return the index of any one of the peak elements. This article discusses the problem, a binary search-based solution, and its implementation in C++.

Problem Statement

You are given an integer array nums where:

• nums[i] is not necessarily unique.
• Two adjacent elements are considered neighbors.

Your task is to find an index i such that nums[i] > nums[i-1] and nums[i] > nums[i+1]. If the array contains multiple peaks, returning the index of any one is acceptable.

Constraints

1. The array is guaranteed to contain at least one peak.
2. For boundary elements, only one neighbor exists, so they can also be peaks.

Solution Overview

To solve this problem efficiently, we use binary search, which reduces the search space logarithmically, achieving an O(log n) time complexity. Let’s break down the approach:

Key Observations

1. A peak can exist at the boundary (first or last element) or inside the array.
2. At any position mid, if nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1], then nums[mid] is a peak.
3. If nums[mid] < nums[mid+1], then a peak must exist to the right of mid.
4. Similarly, if nums[mid] < nums[mid-1], a peak must exist to the left of mid.

Using these observations, we can divide the search space iteratively until a peak is found.

Implementation

Here is the C++ implementation:

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        // Edge cases for small arrays
        if(nums.size() == 1) {
            return 0;
        }
        if(nums[0] > nums[1]) return 0;
        if(nums[nums.size() - 1] > nums[nums.size() - 2]) return nums.size() - 1;
        int low = 1; // Start from the second element
        int high = nums.size() - 2; // End at the second last element
        while (low <= high) {
            int mid = low + (high - low) / 2; // Avoid overflow
            // Check if mid is a peak
            if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
                return mid;
            }
            // Move towards the right if the right neighbor is larger
            else if (nums[mid] < nums[mid + 1]) {
                low = mid + 1;
            }
            // Move towards the left otherwise
            else {
                high = mid - 1;
            }
        }
        return -1; // This should never be reached
    }
};

Explanation

Edge Case Handling:

• If the array has only one element, return its index (0).
• Check if the first or last element is a peak.

Binary Search:

• Set low to 1 and high to nums.size() - 2 to exclude boundary cases.
• Use a loop to iteratively halve the search space.
• Depending on the relative values of nums[mid], adjust low or high.

Return Condition:

• The loop exits once a peak is found, which is guaranteed by the problem constraints.

Time and Space Complexity

Time Complexity

• The binary search algorithm works in O(log n) time.

Space Complexity

• The solution uses constant extra space, making the space complexity O(1).

Example Walkthrough

Consider the array nums = [1, 2, 3, 1]:

Initially, low = 1, high = 2.

Compute mid = 1 + (2 - 1) / 2 = 1.

Check nums[mid] (2):

• nums[mid] > nums[mid - 1] (1) is true.
• nums[mid] < nums[mid + 1] (3) is true.
• Move low to mid + 1 (2).

Compute mid = 2:

• nums[mid] > nums[mid - 1] (2) is true.
• nums[mid] > nums[mid + 1] (1) is true.
• Return mid = 2.

Output: 2 (Index of peak 3).

Summary

The peak element problem is a great exercise for understanding binary search in non-standard scenarios. By leveraging the mathematical guarantees in the problem, we significantly reduce the complexity from O(n) (linear search) to O(log n). This approach is both efficient and elegant, showcasing the power of binary search.

Have questions or suggestions? Let’s discuss in the comments below!