给你一个 山脉数组 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() - 会返回该数组的长度

    示例 1：
    输入：array = [1,2,3,4,5,3,1], target = 3
    输出：2
    解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。
    示例 2：

    输入：array = [0,1,2,4,2,1], target = 3
    输出：-1
    解释：3 在数组中没有出现，返回 -1。

    1. /**
    2.  * // This is the MountainArray's API interface.
    3.  * // You should not implement it, or speculate about its implementation
    4.  * class MountainArray {
    5.  *   public:
    6.  *     int get(int index);
    7.  *     int length();
    8.  * };
    9.  */
    11. class Solution {
    12. public:
    13.     int binary_search1(int target, MountainArray & mountainArr, int left, int right){
    14.         while(left <= right){
    15.             int mid = (left + right) >> 1;
    16.             int cur = mountainArr.get(mid);
    17.             if (target == cur)
    18.                 return mid;
    19.             else if(target < cur)
    20.                 right = mid-1;
    21.             else
    22.                 left = mid+1;
    23.         }
    24.         return -1;
    25.     }
    27.     int binary_search2(int target, MountainArray & mountainArr, int left, int right){
    28.         while(left <= right){
    29.             int mid = (left + right) >> 1;
    30.             int cur = mountainArr.get(mid);
    31.             if (target == cur)
    32.                 return mid;
    33.             else if(target < cur)
    34.                 left = mid+1;
    35.             else
    36.                 right = mid-1;
    37.         }
    38.         return -1;
    39.     }
    41.     int findInMountainArray(int target, MountainArray &mountainArr) {
    42.         // binary search for find peak idx
    43.         int len = mountainArr.length();
    44.         int left = 0, right = len - 1;
    45.         while(left < right){
    46.             int mid = (left + right) >> 1;
    47.             if (mountainArr.get(mid) < mountainArr.get(mid+1))
    48.                 left = mid+1;
    49.             else
    50.                 right = mid-1;
    51.         }
    52.         int peak = left;
    53.         int ans_idx = binary_search1(target, mountainArr, 0, peak);
    54.         if (ans_idx >= 0)
    55.             return ans_idx;
    56.         return binary_search2(target, mountainArr, peak+1, len-1);
    57.     }
    58. };

    欢迎交流，批评指正！