来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-in-mountain-array

1 题目

给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
如果不存在这样的下标 index，就请返回 -1。
何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：
首先，A.length >= 3
其次，在 0 < i < A.length - 1 条件下，存在 i 使得：

• A[0] < A[1] < ... A[i-1] < A[i]
• A[i] > A[i+1] > ... > A[A.length - 1

你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
MountainArray.length() - 会返回该数组的长度

---

/**
 * // 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 {
    public int findInMountainArray(int target, MountainArray mountainArr) {
      
    }
}

2 JAVA解答

首先二分法找出峰值，然后向峰值左侧进行二分查找等于target的值，如果无法找到向峰值右侧进行二分查找。

时间复杂度O(logN)，空间复杂度O(1)

/**
 * // 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 {
    public int findInMountainArray(int target, MountainArray mountainArr) {
       int len = mountainArr.length();
       // 声明山峰值、山峰索引、二分法开始索引、二分法结束索引
       int max,mi,bi = 0,ei = len-1;
       int hi = (ei-bi)/2+bi;
        // 主程:二分法查找顶点坐标，mountainArr一定存在期望值，可以设置死循环
        while (true){
            int center = mountainArr.get(hi);
            int left = mountainArr.get(hi-1);
            int right = mountainArr.get(hi+1);
            if(center>left && center>right){
                max = center;
                break;
            }else if(center<left){
                ei = hi;
            }else if(center<right){
                bi = hi;
            }
            hi = (ei-bi)/2+bi;
        }
        mi = hi;
        if(target==max){
            return mi;
        }
        // 向左二分找target
        bi = 0;
        ei = mi-1;
        hi = (ei-bi)/2+bi;
        while (true){
            int mn = mountainArr.get(hi);
            if(mn==target){
                return hi;
            }else if(mn>target){
                ei = hi;
            }else {
                bi = hi;
            }
            hi = (ei-bi)/2+bi;
            if(hi==bi ||hi==ei){
                if(mountainArr.get(bi)==target){
                    return bi;
                }else if(mountainArr.get(ei)==target){
                    return ei;
                }else{
                    break;
                }
            }
        }
        // 向右二分
        bi = mi;
        ei = len-1;
        hi = (ei-bi)/2+bi;
        while (true){
            int mn = mountainArr.get(hi);
            if(mn==target){
                return hi;
            }else if(mn<target){
                ei = hi;
            }else {
                bi = hi;
            }
            hi = (ei-bi)/2+bi;
            if(hi==bi ||hi==ei){
                if(mountainArr.get(bi)==target){
                    return bi;
                }else if(mountainArr.get(ei)==target){
                    return ei;
                }else{
                    break;
                }
            }
        }
        return -1;
    }
}