LeetCode //C - 162. Find Peak Element

162. Find Peak Element

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

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = $-\infty$. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.
 

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: 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.

Constraints:

• 1 <= nums.length <= 1000
• $-2^{31}<=nums[i]<=2^{31}-1$
• nums[i] != nums[i + 1] for all valid i.

From: LeetCode
Link: 162. Find Peak Element

---

Solution:

Ideas：

1. Binary Search Approach: Instead of checking each element sequentially, we can use binary search. Given that an element is always considered to be strictly greater than its neighbor outside the array, there is always a peak element in the array.

2. Midpoint Calculation: Start with the entire array as the search space. Calculate the midpoint of the current search space.

3. Comparison: Compare the element at the midpoint with its neighbor:

• If nums[mid] is less than nums[mid + 1], then there exists a peak to the right of mid because the elements on the right are increasing. Thus, we can narrow down our search space to the right half.
• If nums[mid] is greater than or equal to nums[mid + 1], then the current element or an element to the left of mid could be a peak. Thus, we narrow down our search to the left half.

4. Convergence: Continue the binary search process until we find a peak element. The process will always converge to a peak because of the properties of the array.

5. Result: Return the index of the peak element.

Code:

int findPeakElement(int* nums, int numsSize) {
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12