算法---二分查找练习-3（山脉数组的顶峰索引）
山脉数组的顶峰索引
- 1. 题目解析
- 2. 讲解算法原理
- 3. 编写代码
1. 题目解析
题目地址：点这里
2. 讲解算法原理
-
初始化两个指针 left 和 right，分别指向数组的起始位置和结束位置。
-
进入循环，循环条件为 left < right。
-
在每次循环中，计算中间元素的索引 mid，通过将左指针 left 和右指针 right 的差值除以2得到。
-
检查中间元素 arr[mid] 和其后一个元素 arr[mid+1] 的大小关系。
-
如果 arr[mid] < arr[mid+1]，说明峰值在中间元素的右侧，将左指针 left 更新为 mid + 1，继续搜索右侧。
-
如果 arr[mid] >= arr[mid+1]，说明峰值在中间元素的左侧或者当前位置就是峰值。将右指针 right 更新为 mid，继续搜索左侧。
- 当循环结束时，左指针 left 指向的位置即为峰值的索引，返回 left 即可得到峰值的位置。
3. 编写代码
class Solution
{
public:
int peakIndexInMountainArray(vector<int>& arr)
{
int left = 1, right = arr.size() - 2;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(arr[mid] > arr[mid - 1]) left = mid;
else right = mid - 1;
}
return left;
}
};