分段二分题目

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;
    }
}