1095. 山脉数组中查找目标值：先二分查找找到山峰，再在山峰两侧分别进行二分查找.md

题目简述：

（这是一个 交互式问题 ）

你可以将一个数组 arr 称为 山脉数组 当且仅当：

• arr.length >= 3
• 存在一些 arr[0] < arr[1] < ... < arr[i - 1] < arr[i] 的 i 使得：
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给定一个山脉数组 mountainArr ，返回 最小 的 index 使得 mountainArr.get(index) == target。如果不存在这样的 index，返回 -1 。

你无法直接访问山脉数组。你只能使用 MountainArray 接口来访问数组：

• MountainArray.get(k) 返回数组中下标为 k 的元素（从 0 开始）。
• MountainArray.length() 返回数组的长度。

调用 MountainArray.get 超过 100 次的提交会被判定为错误答案。此外，任何试图绕过在线评测的解决方案都将导致取消资格。

题目链接：1095. 山脉数组中查找目标值

思路

很明显是一个二分搜索算法的问题嘛！

我们先二分搜索找出山顶，然后再分别在山顶两侧各自应用二分搜索，这样至多启动三例二分搜索算法，就可以找出 target。

---

对于寻找山峰的二分查找，初始化 left = 0、right = MountainArray.length() - 1，

1. 取 mid = left + (right - left) / 2
2. 借助 mid + 1（或 mid - 1 也可以）判断 mid 处于上山还是下山，
   • 若 MountainArray.get(mid) < MountainArray.get(mid + 1)，则 mid 处于上山段，收缩边界，令 left = mid + 1
   • 若 MountainArray.get(mid) > MountainArray.get(mid + 1)，则 mid 处于下山段，收缩边界，令 right = mid
3. 回到第一步，直到 MountainArray.get(mid) > MountainArray.get(mid + 1) 且 MountainArray.get(mid) > MountainArray.get(mid - 1)，此时 mid 即为山峰

对于第三步的条件，可以优化为 while (left < right)，此时 left == right 之处即为山峰。

---

找到了山顶后的二分搜索算法这里就不单独描述了，标准的二分查找。

代码

/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface MountainArray {
 *     public int get(int index) {}
 *     public int length() {}
 * }
 */

class Solution {

    private int[] map;
    private MountainArray mountainArr;

    public int findInMountainArray(int target, MountainArray mountainArr) {
        this.map = new int[mountainArr.length()];
        this.mountainArr = mountainArr;
        Arrays.fill(map, -1);

        // 寻找山峰
        int l = 0;
        int r = mountainArr.length() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (cache(mid) < cache(mid + 1)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        // 在山峰两侧分别二分搜索
        int peak = l;
        if (cache(peak) == target) return peak;
        l = 0;
        r = peak - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (cache(mid) < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (cache(l) == target) return l;

        l = peak + 1;
        r = mountainArr.length() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (cache(mid) > target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (l < mountainArr.length() && cache(l) == target) return l;

        return -1;
    }

    private int cache(int index) {
        if (map[index] == -1) {
            int val = mountainArr.get(index);
            map[index] = val;
            return val;
        } else {
            return map[index];
        }
    }
}