Find Peak Element
A peak element in an array is an element that is not smaller than its neighbors. Given an input array nums, find a peak element and return its index. You may assume that the input array nums contains at least one element and the first and last elements are not peak elements.
Constraints:
- 1 <= nums.length <= 1000
- -2^31 <= nums[i] <= 2^31 - 1
- nums is guaranteed to have a peak element
Examples:
Input: [1,2,3,1]
Output: 2
Explanation: The peak element is 3, which is at index 2
Solutions
Binary Search
The idea is to use binary search to find the peak element. We start by initializing two pointers, left and right, to the start and end of the array. Then, we calculate the mid index and compare the middle element with its next element. If the middle element is smaller than the next element, we know that the peak element must be on the right side, so we update the left pointer to mid + 1. Otherwise, we update the right pointer to mid. We repeat this process until left and right pointers meet, which will be the index of the peak element.
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
}
else {
right = mid;
}
}
return left;
}Follow-up:
What if the input array is not guaranteed to have a peak element?
