1095. Find in Mountain Array

Loading...LeetCode

Mountain array 可以视作是两个单调 array 的拼合，可以分别对两个单调的 subarray 做 binary search 来找 target，这样搜索时间可以控制在 O(logN)，拆分 mountain array （找peak，即逐步缩小单调ascending区间）也需要 O(logN) 的时间。

# """
# 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 isAscending(self, mountain_arr, idx):
        if mountain_arr.get(idx) < mountain_arr.get(idx+1):
            return True
        else: 
            return False
        
    def findPeak(self, mountain_arr, left, right):
        if left == right: 
            return left
        mid = (left + right) // 2
        if self.isAscending(mountain_arr, mid):
            return self.findPeak(mountain_arr, mid+1, right)
        else:
            return self.findPeak(mountain_arr, left, mid)
    
    def binarySearch(self, target, mountain_arr, left, right, ascending:bool):
        mid = (left+right)//2
        vm = mountain_arr.get(mid)
        if vm == target:
            return mid
        if left == right:
            return -1
        if (target > vm and ascending) or (target < vm and not ascending):
            return self.binarySearch(target, mountain_arr, mid+1, right, ascending)
        else:
            return self.binarySearch(target, mountain_arr, left, mid, ascending)
            
    def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
        peak = self.findPeak(mountain_arr, 0, mountain_arr.length()-1)
        res_left = self.binarySearch(target, mountain_arr, 0, peak, ascending=True)
        if res_left != -1:
            return res_left
        else:
            return self.binarySearch(target, mountain_arr, peak+1, mountain_arr.length()-1, ascending=False)