1095. Find in Mountain Array

https://leetcode.com/problems/find-in-mountain-array/

solution

class Solution:
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        r = mountain_arr.length() - 1
        peak_index = self.get_peak(mountain_arr, 0, r)
        l_index = self.search_left(mountain_arr, 0, peak_index, target)

        if l_index != -1:
            return l_index

        r_index = self.search_right(mountain_arr, peak_index, r, target)
        return r_index

    def get_peak(self, mountain_arr, l, r):
        while l < r:
            mid = l + (r - l) // 2
            if mountain_arr.get(mid) < mountain_arr.get(mid+1):
                l = mid + 1
            else:
                r = mid
        return l

    def search_left(self, mountain_arr, l, r, target):
        while l <= r:
            mid = l + (r - l) // 2
            if mountain_arr.get(mid) == target:
                return mid
            elif mountain_arr.get(mid) < target:
                l = mid + 1
            else:
                r = mid - 1
        return -1

    def search_right(self, mountain_arr, l, r, target):
        while l <= r:
            mid = l + (r - l) // 2
            if mountain_arr.get(mid) == target:
                return mid
            elif mountain_arr.get(mid) < target:
                r = mid - 1
            else:
                l = mid + 1
        return -1

时间复杂度：O(log(n)) 空间复杂度：O(1)

follow up

852. Peak Index in a Mountain Array

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l = 0
        r = len(arr) - 1
        while l < r:
            mid = l + (r - l) // 2
            if arr[mid] < arr[mid+1]:
                l = mid + 1

            elif arr[mid] > arr[mid+1]:
                r = mid
        return l

时间复杂度：O(log(n)) 空间复杂度：O(1)