1095. 山脉数组中查找目标值 #

标签：数组、二分查找、交互
难度：困难

题目大意 #

给你一个山脉数组 mountainArr。

要求：返回能够使得 mountainArr.get(index) 等于 target 最小的下标 index 值。如果不存在这样的下标 index，就请返回 -1。

山脉数组：满足以下属性的数组。

len(arr) >= 3；
存在 i（0 < i < len(arr) - 1），使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i];
- arr[i] > arr[i+1] > ... > arr[len(arr) - 1]。

注意：

不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
- MountainArray.get(index)：会返回数组中索引为 k 的元素（下标从 0 开始）。
- MountainArray.length()：会返回该数组的长度。
对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。

解题思路 #

因为题目要求不能对 MountainArray.get 发起超过 100 次调用。所以遍历数组进行查找是不可行的。

根据山脉数组的性质，我们可以把山脉数组分为两部分：「前半部分的升序数组」和「后半部分的降序数组」。在有序数组中查找目标值可以使用二分查找来减少查找次数。

而山脉的峰顶元素索引也可以通过二分查找来做。所以这道题我们可以分为三步：

通过二分查找找到山脉数组的峰顶元素索引。
通过二分查找在前半部分的升序数组中查找目标元素。
通过二分查找在后半部分的降序数组中查找目标元素。

最后，通过对查找结果的判断来输出最终答案。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def binarySearchPeak(self, mountain_arr) -> int:
        left, right = 0, mountain_arr.length() - 1
        while left < right:
            mid = left + (right - left) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid + 1):
                left = mid + 1
            else:
                right = mid
        return left

    def binarySearchAscending(self, mountain_arr, left, right, target):
        while left < right:
            mid = left + (right - left) // 2
            if mountain_arr.get(mid) < target:
                left = mid + 1
            else:
                right = mid
        return left if mountain_arr.get(left) == target else -1

    def binarySearchDescending(self, mountain_arr, left, right, target):
        while left < right:
            mid = left + (right - left) // 2
            if mountain_arr.get(mid) > target:
                left = mid + 1
            else:
                right = mid
        return left if mountain_arr.get(left) == target else -1

    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        size = mountain_arr.length()
        peek_i = self.binarySearchPeak(mountain_arr)

        res_left = self.binarySearchAscending(mountain_arr, 0, peek_i, target)
        res_right = self.binarySearchDescending(mountain_arr, peek_i + 1, size - 1, target)
        
        return res_left if res_left != -1 else res_right