山脉数组中查找目标值

给你一个 山脉数组 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。
 

提示：

3 <= mountain_arr.length() <= 10000
0 <= target <= 10^9
0 <= mountain_arr.get(index) <= 10^9

这道题的核心就是二分查找，我们只需要通过二分查找找到转折点，之后再通过二分查找找到目标值即可。

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

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int l = 0,r = mountainArr.length()-1;
        int mid = (l+r)/2;
        int peak = 0;
        while(true)
        {
            if(mountainArr.get(mid)>mountainArr.get(mid+1))
            {
                if(l==mid)
                {
                    peak = mid;
                    break;
                }
                r = mid;
            }
            else
            {
                if(l==mid)
                {
                    peak = mid+1;
                    break;
                }
                l = mid;
            }
            mid = (l+r)/2;
        }
        l = 0,r = peak;
        cout<<peak<<endl;
        mid = (l+r)/2;
        while(true)
        {
            if(target>mountainArr.get(mid))
            {
                if(l!=mid)
                    l = mid;
                else
                {
                    if(target==mountainArr.get(r))
                        return r;
                    else
                        break;
                }
            }
            else if(target<mountainArr.get(mid))
            {
                if(r!=mid)
                    r = mid;
                else
                {
                    if(target==mountainArr.get(l))
                        return l;
                    else
                        break;
                }
            }
            else
            {
                return mid;
            }
            mid = (l+r)/2;
        }
        l = peak+1,r = mountainArr.length()-1;
        mid = (l+r)/2;
        while(true)
        {
            if(target>mountainArr.get(mid))
            {
                if(r!=mid)
                    r = mid;
                else
                {
                    if(target==mountainArr.get(l))
                        return l;
                    else
                        break;
                }
            }
            else if(target<mountainArr.get(mid))
            {
                if(l!=mid)
                    l = mid;
                else
                {
                    if(target==mountainArr.get(r))
                        return r;
                    else
                        break;
                }
            }
            else
            {
                return mid;
            }
            mid = (l+r)/2;
        }
        return -1;
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-in-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

山脉数组中查找目标值

原文：https://www.cnblogs.com/gxyssd/p/12800127.html