1095. 山脉数组中查找目标值（Rating 1827）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

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

Rating 1827

思路

显然二分。

首先二分找到山脉峰值

接着分别二分前后找到目标值

二分找山峰的地方没有想出来，关键思路：

二分过程中比较mid和mid+1对应的值

• 如果mid的值小于mid+1的值，那么山峰肯定在mid+1及其右边
• 如果mid的值大于mid+1的值，那么山峰肯定在mid及其左边

代码

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
#class MountainArray:
#    def get(self, index: int) -> int:
#    def length(self) -> int:

class Solution:
    def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
        n = mountainArr.length()
        # find peak
        l, r = 0, n - 1
        while l < r: # 因为要比较mid和mid+1的值，所以这里不能取等
            m = (l + r) // 2
            m0_num = mountainArr.get(m)
            m1_num = mountainArr.get(m + 1)
            if m0_num < m1_num:
                l = m + 1
            else:
                r = m
        peak_idx = l # 找到峰值
        # find left
        l, r = 0, peak_idx
        while l <= r:
            m = (l + r) // 2
            m_num = mountainArr.get(m)
            if m_num == target:
                return m
            if m_num > target:
                r = m - 1
            else:
                l = m + 1
        # find right
        l, r = peak_idx, n - 1
        while l <= r:
            m = (l + r) // 2
            m_num = mountainArr.get(m)
            if m_num == target:
                return m
            if m_num > target:
                l = m + 1
            else:
                r = m - 1
        return -1