[数据结构与算法]leetcode 1095.山脉数组中查找目标

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()?- 会返回该数组的长度

?

注意：

对?MountainArray.get?发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。

为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，请注意这 不是一个正确答案。

?

示例 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

?

2、解题思路

这种数组中找到一个值；一般的思路都是暴力破解，但是暴力破解的时间复杂度有的不符合要求；

这种山峰形状的数组，两边都是有序的，所以很容易就想到用二分查找来解决问题：这个时候就二分来判断怎么分，怎么找目标值

（1）解决方案一：暴力破解；遍历两个指针记录起始位置和终止位置（时间复杂度为o(n)，空间复杂度为o(1)）

（2）解决方案二：二分查找；（时间复杂度为o(logn)，空间复杂度为o(1)）

步骤一：先找到中间峰值（如果峰值等于目标值直接返回）

步骤二：在左边有序的区间用二分查找找到目标值坐标（如果找到直接返回；没有找到进行步骤三）

步骤三：在右边有序的区间用二分查找找到目标值坐标

?

3、java代码

    public static int findInMountainArray(int target, MountainArray mountainArr) {

        int monuntainindex=peakIndexInMountainArray(mountainArr);  //先找到峰顶元素
        if(mountainArr.get(monuntainindex)==target) return monuntainindex;  //如果等于峰顶元素则直接返回

        int leftindex=searchLeft(target,mountainArr,monuntainindex);  //在左边进行二分查找(左边是递增序列)
        if(leftindex!=-1)return leftindex; //如果左边找到了直接返回

        int rightindex=searchRight(target,mountainArr,monuntainindex);  //在左边进行二分查找(左边是递增序列)
        return rightindex; //如果左边没找到直接返回右边的值，右边找到了就返回下标，没有就返回-1



    }
    //找到峰顶元素
    public static  int peakIndexInMountainArray(MountainArray arr) {
        if(arr==null || arr.length()==0) return 0;
        int left = 0;
        int right = arr.length() - 1;
        while (left < right) {
            int mid=left+(right-left)/2;
            if(arr.get(mid)<arr.get(mid+1)){ //往右爬山
                left=mid+1;
            }else{ //往左爬山
                right=mid; //同样的因为mid比较大，所以mid也可能是最大值
            }
        }
        return left;
    }

    //在左边找到目标值
    public static  int searchLeft(int target, MountainArray nums,int rightIndex) {
        int left = 0;
        int right = rightIndex-1;

        while (left <= right) {
            int mid = left+(right-left) / 2;
            if (nums.get(mid) < target) {
                left = mid+ 1;
            } else if (nums.get(mid) > target) {
                right = mid - 1;
            } else{ return mid; } }
        return -1;
    }

    //在右边找到目标值
    public static int searchRight(int target, MountainArray nums,int leftIndex ) {
        int left = leftIndex+1;
        int right = nums.length() - 1;

        while (left <= right) {
            int mid = left+(right-left) / 2;
            if (nums.get(mid) < target) {
                right = mid-1;
            } else if (nums.get(mid) > target) {
                left = mid + 1;
            } else{ return mid; } }
        return -1;
    }