题目：
符合下列属性的数组 arr 称为 山脉数组 ：
- arr.length >= 3
- 存在 i（0 < i < arr.length - 1）使得：
- arr[0] < arr[1] < ... arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]
- 给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
示例 1：
输入：arr = [0,1,0]
输出：1
示例 2：
输入：arr = [0,2,1,0]
输出：1
示例 3：
输入：arr = [0,10,5,2]
输出：1
示例 4：
输入：arr = [3,4,5,1]
输出：2
示例 5：
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2
提示：
- 3 <= arr.length <= 104
- 0 <= arr[i] <= 106
- 题目数据保证 arr 是一个山脉数组
进阶：很容易想到时间复杂度 O(n) 的解决方案，你可以设计一个 O(log(n)) 的解决方案吗？
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/peak-index-in-a-mountain-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
【二分查找】
其实看到提示中进阶要求设计时间复杂度为O(log(n))的时候就会想到二分查找，加上题目中给定的数组可以看做两个有序的数组，先升序（上山）后降序（下山），目的就是找到升序中最后的那一个数字（山顶）的下标。用二分查找：
- 初始化左右边界：left = 0, right = n - 1,计算出mid
- 循环条件是：left < right，判断的条件就让mid与 mid - 1的数值进行判断
- arr[mid] > = arr[mid - 1]：说明mid还处于上山阶段，此时mid有可能就是山顶，需要往右继续找山顶，搜索区间变为[mid, right]，即让left = mid（注意：mid需要向上取整）；
- arr[mid] < arr[mid-1]：说明mid已经处于下山阶段，就需要往左寻找山顶，搜索区间变为[left, mid - 1]，即让right = mid - 1;
- 循环结束的条件是：left == right，题目中说了 arr 是一个山脉数组，那么最后一定会是山顶，直接返回 left 或者 right 即可。
java代码（left < right）：
1 class Solution {
2 public int peakIndexInMountainArray(int[] arr) {
3 int n = arr.length;
4 int left = 0, right = n - 1;
5 while (left < right){
6 int mid = left + (right - left + 1) / 2;
7 if (arr[mid] > arr[mid -1]){
8 left = mid;
9 }else{
10 right = mid - 1;
11 }
12 }
13 return left;
14 }
15 }
python3代码（left <= right）:错误代码：
1 class Solution: 2 def peakIndexInMountainArray(self, arr: List[int]) -> int: 3 left, right = 0, len(arr) - 1 4 while left <= right: 5 mid = left + (right - left) // 2 6 if arr[mid] > arr[mid - 1] and arr[mid] > arr[mid + 1]: 7 return mid 8 # arr[mid] > arr[mid - 1]并且arr[mid] <= arr[mid + 1] 9 # mid + 1更大 10 elif arr[mid] > arr[mid - 1]: 11 left = mid + 1 12 else: 13 # arr[mid] > arr[mid + 1]并且arr[mid]<= arr[mid -1] 14 # mid - 1更大 15 right = mid - 1 16 return -1
有一个测试用例过不去：
研究一下它为什么过不去：
[3,9,8,6,4]
①left = 0, right = 4, mid = 2, arr[2] > arr[3]且arr[2] < arr[1]故right = mid -1 = 1;
②left = 0, right = 1,mid = 0, 这时mid -1 = -1已经数组越界了，故为了避免这种判断，arr[mid+1] > arr[mid] 必须写在 arr[mid-1]>arr[mid] 前面判断。跟着正确的，arr[1] > arr[0]，left = mid + 1 = 1;
③left = 1,right = 1,mid = 1，arr[0] < arr[1] < arr[2]，故直接返回mid = 1。
python3正确代码：
1 class Solution: 2 def peakIndexInMountainArray(self, arr: List[int]) -> int: 3 left, right = 0, len(arr) - 1 4 while left <= right: 5 mid = left + (right - left) // 2 6 if arr[mid] > arr[mid + 1] and arr[mid] > arr[mid - 1]: 7 return mid 8 # arr[mid] > arr[mid + 1]并且arr[mid]<= arr[mid -1] 9 # mid - 1更大 10 elif arr[mid] > arr[mid + 1]: 11 right = mid - 1 12 else: 13 # arr[mid] > arr[mid - 1]并且arr[mid] <= arr[mid + 1] 14 # mid + 1更大 15 left = mid + 1 16 return -1
