LeetCode.1095.Find in Mountain Array 山脉数组中查找目标值

题目描述

1095 Find in Mountain Array
https://leetcode-cn.com/problems/find-in-mountain-array/

（这是一个 交互式问题 ）

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

---

解题过程

三次二分搜索
1、先通过二分搜索找到峰值所在下标，二分的策略是如果 mid 位于左侧升序子数组上，则峰值肯定在 mid 右侧；相反，如果 mid 位于右侧降序子数组上，则峰值肯定在 mid 左侧
2、找到峰值下标后，先在左侧二分搜索
3、若左侧没有，在右侧二分搜索

看了题解后发现找峰值的二分搜索写的复杂了， 我比较了 mid 左右的元素，其实只需 mid 和他左侧（或右侧）的一个元素对比就行了

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

// 山脉数组接口
interface MountainArray {
    public int get(int index);
    public int length();
}

// 山脉数组实现类
class MyMountainArray implements MountainArray {
    private int[] array;

    MyMountainArray(int[] arr) {
        this.array = arr;
    }

    @Override
    public int get(int index) {
        return array[index];
    }

    @Override
    public int length() {
        return array.length;
    }
}

private static class SolutionV2020 {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        // 找峰值下标
        int peekIndex = findPeek(mountainArr);
        if (mountainArr.get(peekIndex) == target) {
            return peekIndex;
        }
        // 在峰值左侧升序序列中二分搜索
        if (peekIndex - 1 >= 0) {
            int leftRes = binarySearch(mountainArr, 0, peekIndex - 1, target, true);
            if (leftRes != -1) {
                return leftRes;
            }
        }
        // 在峰值右侧降序序列中二分搜索
        int length = mountainArr.length();
        if (peekIndex + 1 < length) {
            int rightRes = binarySearch(mountainArr, peekIndex + 1, length -1, target, false);
            return rightRes;
        }
        return -1;
    }

    // 二分搜索找山峰数组中峰值的下标
    private int findPeek(MountainArray mountainArr) {
        int length = mountainArr.length();
        int left = 0, right = length -1 ;
        while (left <= right) {
            if (right - left < 2) {
                return mountainArr.get(left) > mountainArr.get(right) ? left : right;
            }
            int mid = left + (right - left) / 2;
            int midValue = mountainArr.get(mid), midLeftValue = mountainArr.get(mid - 1), midRightValue = mountainArr.get(mid + 1);
            if (midValue > midLeftValue && midValue > midRightValue) {
                return mid;
            } else if (midValue > midLeftValue && midValue < midRightValue) {
                // mid在左升序序列中，则峰值在右侧
                left = mid + 1;
            } else {
                // mid在右降序序列中，则峰值在左侧
                right = mid - 1;
            }
        }
        return 0;
    }

    /**
     * 在有序数组 mountainArray[start...end] 中二分查找 target，找不到返回-1
     * @param mountainArray
     * @param start
     * @param end
     * @param target
     * @param asc true: 升序，false 降序
     * @return
     */
    private int binarySearch(MountainArray mountainArray, int start, int end, int target, boolean asc) {
        int left = start, right = end;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = mountainArray.get(mid);
            if (midValue == target) {
                return mid;
            } else if (midValue < target) {
                if (asc) {
                    left = mid + 1;
                } else {
                    right = mid -1;
                }
            } else {
                if (asc) {
                    right = mid -1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_1095_FindInMountainArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_1095_FindInMountainArray.java

---