1095. 山脉数组中查找目标值
image.png
思路还是比较统一的，首先是用二分法找出数组里面的峰值，然后再进行两次二分法。这边用的二分法的思路不是一般的left<=right，而是采用left+1<right，然后再判断targat到底是left还是right值。
//这个是leetcode可ac版本
class Solution {
public int findInMountainArray(int target, MountainArray mountainArr) {
// 先找到峰顶索引 peakIdx
int lo = 0, hi = mountainArr.length() - 1;
while (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
int midVal = mountainArr.get(mid);
if (midVal > mountainArr.get(mid - 1)) {
lo = mid;
} else {
hi = mid;
}
}
int peakIdx = mountainArr.get(lo) > mountainArr.get(hi)? lo: hi;
// 根据峰顶将山脉数组分为「升序数组」和「降序数组」两段，分别进行二分查找
int idx = binSearch(mountainArr, 0, peakIdx, target, true);
return idx != -1? idx: binSearch(mountainArr, peakIdx + 1, mountainArr.length() - 1, target, false);
}
private int binSearch(MountainArray mountainArr, int lo, int hi, int target, boolean asc) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int midVal = mountainArr.get(mid);
if (midVal == target) {
return mid;
}
if (midVal < target) {
lo = asc? mid + 1: lo;
hi = asc? hi: mid - 1;
} else {
hi = asc? mid - 1: hi;
lo = asc? lo: mid + 1;
}
}
return -1;
}
}
