# Leetcode 1095. Find in Mountain Array

## 題解

先用二分搜索找到山峰值，在把數組切兩半使用二分搜索查找目標，這邊要注意，右邊的數組會是反的，所以要把二分查找的邏輯反過來查找即可。

# """
# 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, mountain_arr: 'MountainArray') -> int:
        # Time complexity: O(n)
        # Space complexity: O(1)
        n = mountain_arr.length()
        def find_mountain(): # 二分搜索查找山峰
            nonlocal n
            left = 1
            right = n - 2
            while left < right:
                mid = left + (right - left) // 2
                prev = mountain_arr.get(mid)
                curr = mountain_arr.get(mid + 1)
                if prev < curr:
                    left = mid + 1
                else:
                    right = mid
            return left
        def binary_search(left: int, right: int,reverse: bool): # 常規二分搜索
            nonlocal target,n
            while left <= right:
                mid = left + (right - left) // 2
                num = mountain_arr.get(mid)
                if num == target:
                    return mid
                elif num < target:
                    # 反過來查找
                    if reverse:
                        right = mid - 1
                    else:
                        left = mid + 1
                else:
                    # 反過來查找
                    if reverse:
                        left = mid + 1
                    else:
                        right = mid - 1    
            return -1
        mountain = find_mountain()
        result = binary_search(0,mountain,False) # 先查找左邊的，因為題目要求最小
        if result == -1: # 如果左邊沒有在查找右邊的
            result = binary_search(mountain+1,n-1,True)
        return result