题目描述
思路：用二分进行排除不满足条件的元素，最后剩下的元素即为答案
往常我们使用「二分」进行查值，需要确保序列本身满足「二段性」：当选定一个端点（基准值）后，结合「一段满足 & 另一段不满足」的特性来实现“折半”的查找效果。
但本题求的是峰顶索引值，如果我们选定数组头部或者尾部元素，其实无法根据大小关系“直接”将数组分成两段。
但可以利用题目发现如下性质：由于 arr 数值各不相同，因此峰顶元素左侧必然满足严格单调递增，峰顶元素右侧必然不满足。
因此 以峰顶元素为分割点的 arr 数组，根据与 前一元素/后一元素 的大小关系，具有二段性：
- 峰顶元素左侧满足 arr[i−1]<arr[i]arr[i-1] < arr[i]arr[i−1]<arr[i] 性质，右侧不满足
- 峰顶元素右侧满足 arr[i]>arr[i+1]arr[i] > arr[i+1]arr[i]>arr[i+1] 性质，左侧不满足
方法一：
class Solution {
public int peakIndexInMountainArray(int[] arr) {
// 有题目可知:i(0 < i < arr.length - 1) 左闭右闭区间
int left = 1, right = arr.length - 2;
while (left <= right) {
if (left == right) return left;
int mid = left + (right - left) / 2;
// mid与mid + 1进行比较,排除不符合的元素
if (arr[mid] < arr[mid + 1]){ // 在右边找
left = mid + 1;
} else if (arr[mid] > arr[mid + 1]) { // 在左边找,但mid可能为峰值
right = mid;
}
}
throw new RuntimeException("Error");
}
}