Problem
Given an integer arraynums, find a peak element and return its index. An element is a peak if it is strictly greater than its neighbors.
You may assume that
nums[-1] = nums[n] = -∞. The array may contain multiple peaks, so returning the index of any peak is valid.
Example(s)
Example 1
Input
nums = [1,2,3,1]Output
2Example 2
Input
nums = [1,2,1,3,5,6,4]Output
5Solution
This problem uses Binary Search. Compare the middle element with the next element. Ifnums[mid] > nums[mid + 1], a peak exists on the left side including mid. Otherwise, a peak must exist on the right side.
Continue reducing the search range until both boundaries meet. The remaining index is a peak.
class Solution {
public int findPeakElement(int[] nums) {
return binarySearch(0, nums.length - 1, nums);
}
private int binarySearch(int i, int j, int[] nums) {
if (i >= j) {
return i;
}
int mid = i + (j - i) / 2;
if (nums[mid] > nums[mid + 1]) {
return binarySearch(i, mid, nums);
} else {
return binarySearch(mid + 1, j, nums);
}
}
}