山脉数组中查找目标值

标签: 数组二分查找交互

难度: Hard

（这是一个 交互式问题 ）

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

Submission

运行时间: 23 ms

内存: 16.7 MB

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        n = mountain_arr.length()
        peak = self.findPeak(mountain_arr, 0, n - 1)
        
        # 在递增部分查找
        left_result = self.binarySearch(mountain_arr, 0, peak, target, True)
        if left_result != -1:
            return left_result
        
        # 在递减部分查找
        right_result = self.binarySearch(mountain_arr, peak + 1, n - 1, target, False)
        return right_result
    
    def findPeak(self, mountain_arr: 'MountainArray', left: int, right: int) -> int:
        while left < right:
            mid = (left + right) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        return left
    
    def binarySearch(self, mountain_arr: 'MountainArray', left: int, right: int, target: int, ascending: bool) -> int:
        while left <= right:
            mid = (left + right) // 2
            if mountain_arr.get(mid) == target:
                return mid
            
            if ascending:
                if mountain_arr.get(mid) < target:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if mountain_arr.get(mid) > target:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1

Explain

这个解决方案首先利用二分搜索找到山脉数组的峰值，即从左到右最大的元素，这个元素将数组分为递增和递减两部分。找到峰值后，解决方案再次使用二分搜索在递增部分查找目标值。如果在递增部分找到了目标值，直接返回其索引。如果没有找到，再在递减部分使用二分搜索查找目标值。如果在任何部分都没有找到目标值，则返回-1。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        n = mountain_arr.length()
        peak = self.findPeak(mountain_arr, 0, n - 1)
        
        # 在递增部分查找
        left_result = self.binarySearch(mountain_arr, 0, peak, target, True)
        if left_result != -1:
            return left_result
        
        # 在递减部分查找
        right_result = self.binarySearch(mountain_arr, peak + 1, n - 1, target, False)
        return right_result
    
    def findPeak(self, mountain_arr: 'MountainArray', left: int, right: int) -> int:
        # 使用二分搜索找到峰值
        while left < right:
            mid = (left + right) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        return left
    
    def binarySearch(self, mountain_arr: 'MountainArray', left: int, right: int, target: int, ascending: bool) -> int:
        # 根据数组的增减性质选择适当的二分搜索方向
        while left <= right:
            mid = (left + right) // 2
            if mountain_arr.get(mid) == target:
                return mid
            
            if ascending:
                if mountain_arr.get(mid) < target:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if mountain_arr.get(mid) > target:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1

Explore

在二分搜索过程中，我们比较中间元素和其右侧相邻的元素。如果中间元素小于其右侧元素，则表明峰值位于中间元素的右侧（包括中间元素的右侧元素），因此我们将搜索区间调整为右侧部分，即移动左边界`left`到`mid + 1`。反之，如果中间元素大于或等于其右侧元素，则峰值位于中间元素的左侧（包括中间元素本身），因此我们将搜索区间调整为左侧部分，即移动右边界`right`到`mid`。最终当`left`等于`right`时，它们指向的位置即为峰值位置。

山脉数组的定义是先递增再递减，因此在找到峰值后，我们可以明确两个部分：左侧部分是递增的，右侧部分是递减的。递增部分和递减部分都是单调的，这使得我们可以分别在这两个部分使用二分搜索来高效查找目标值。二分搜索有效的前提是数据的单调性，单调递增或递减的数组允许我们通过比较中间值与目标值来快速决定继续搜索的方向，从而有效地减少搜索范围。

在递增部分的二分搜索中，如果中间元素小于目标值，则目标值可能位于中间元素的右侧，因此我们将左边界`left`移动到`mid + 1`。如果中间元素大于目标值，目标值可能位于中间元素的左侧，因此我们将右边界`right`移动到`mid - 1`。在递减部分的二分搜索中，逻辑相反：如果中间元素大于目标值，则目标值可能位于中间元素的右侧，因此我们将左边界`left`移动到`mid + 1`；如果中间元素小于目标值，则目标值可能位于中间元素的左侧，因此我们将右边界`right`移动到`mid - 1`。这样的调整是为了确保我们总是向可能包含目标值的区域缩小搜索范围。