Leetcode # 1095. Find in Mountain Array

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

相關例題

Leetcode # 852. Peak Index in a Mountain Array

Solution

1. 先找到山頂（參考 Leetcode # 852. Peak Index in a Mountain Array ）
2. 從山頂將 array 一分為二
   各別做 binary search（要注意是遞增或遞減）

Time Complexity: O(log(len(mountain_arr)))
Space Complexity: O(1)

class Solution:
  def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
    length = mountain_arr.length()
    l, r = 0, length - 1
    value = {
      l: mountain_arr.get(l), 
      r: mountain_arr.get(r)
    }
    if value[l] == target:
      return l
    
    # find top, ref leetcode # 852
    while l < r:
      mid = (l + r) // 2
      for i in range(2):
        if mid + i not in value:
          value[mid + i] = mountain_arr.get(mid + i)
      if value[mid + 1] - value[mid] > 0:
        l = mid + 1
      else:
        r = mid
        
    top = l
    
    if value[top] < target:
      return -1
    
    # binary search
    for line in [(0, top), (top, length -1)]:
      # ascend or descend
      sign = 1 if value[line[1]] > value[line[0]] else -1
      if min(value[line[0]], value[line[1]]) > target:
        continue
      l, r = line
      while l <= r:
        print(l, r)
        mid = (l + r) // 2
        if mid not in value:
          value[mid] = mountain_arr.get(mid)
        if value[mid] == target:
          return mid
        elif sign * value[mid] < sign * target:
          l = mid + 1
        else:
          r = mid - 1
        
    return -1

Last Updated on 2023/08/16 by A1go