@TOC

# # 题目描述

1. 首先，`A.length >= 3`
2. 其次，在 `0 < i < A.length - 1` 条件下，存在 `i` 使得：
• `A[0] < A[1] < ... A[i-1] < A[i]`
• `A[i] > A[i+1] > ... > A[A.length - 1]`

• `MountainArray.get(k)` - 会返回数组中索引为k 的元素（下标从 0 开始）
• `MountainArray.length()` - 会返回该数组的长度

``````输入：array = [1,2,3,4,5,3,1], target = 3

``````

``````输入：array = [0,1,2,4,2,1], target = 3

``````

1. `3 <= mountain_arr.length() <= 10000`
2. `0 <= target <= 10^9`
3. `0 <= mountain_arr.get(index) <= 10^9`

# # 解题方法

## # 二分查找

1. 找到山峰的位置
2. 在山峰的左边查找 target
3. 如果查找不到，则在山峰的右边查找 target

Python 代码如下：

``````# """
# 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, nums: 'nums') -> int:
N = nums.length()
peek = self.findPeek(target, nums)
left_index = self.findInAscOrder(target, nums, 0, peek)
right_index = self.findInDecOrder(target, nums, peek, N - 1)
if left_index != -1:
return left_index
else:
return right_index

def findPeek(self, target, nums):
N = nums.length()
left, right = 1, N - 2
while left <= right:
mid = left + (right - left) // 2
if nums.get(mid - 1) < nums.get(mid) > nums.get(mid + 1):
return mid
elif nums.get(mid - 1) < nums.get(mid) < nums.get(mid + 1):
left = mid + 1
else:
right = mid - 1
return left

def findInAscOrder(self, target, nums, begin, end):
left, right = begin, end
while left <= right:
mid = left + (right - left) // 2
print(left, right, mid)
cur = nums.get(mid)
if cur == target:
return mid
elif cur < target:
left = mid + 1
else:
right = mid - 1
return -1

def findInDecOrder(self, target, nums, begin, end):
left, right = begin, end
while left <= right:
mid = left + (right - left) // 2
cur = nums.get(mid)
if cur == target:
return mid
elif cur < target:
right = mid - 1
else:
left = mid + 1
return -1
``````

# # 日期

2020 年 4 月 29 日 —— 连续刷二分