山脉数组的峰顶索引（二分查找）1

标题中的“山脉数组的峰顶索引（二分查找）1”指的是在计算机科学和算法设计中，如何在一个特殊的数组结构——山脉数组中找到峰值元素的索引，使用二分查找算法来提高效率。这个题目来自LeetCode，一个在线编程挑战平台，常用于练习和面试准备。 描述中提到的“山脉数组”具有以下特征： 1. 数组长度至少为3。 2. 存在一个索引i（0 < i < arr.length - 1），使得数组从前到后先递增，到达i位置时达到最大值，然后开始递减。 给定一个整数数组arr，目标是找到这个峰值元素的索引，即满足arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]的索引i。 示例展示了不同的山脉数组及其对应的峰顶索引： - 示例1：输入arr = [0,1,0]，输出1，因为arr[1]是峰值。 - 示例2：输入arr = [0,2,1,0]，输出1，同上。 - 示例3：输入arr = [0,10,5,2]，输出1，因为arr[1]是峰值。 - 示例4：输入arr = [3,4,5,1]，输出2，因为arr[2]是峰值。 - 示例5：输入arr = [24,69,100,99,79,78,67,36,26,19]，输出2，因为arr[2]是峰值。 在提供的解决方案中，有两种方法找到峰顶索引： 1. **一次线性遍历**：从头开始遍历数组，直到找到第一个比其相邻元素小的元素，返回前一个元素的索引。这种方法的时间复杂度为O(n)，其中n是数组长度。 2. **二分查找**：这是更高效的方法，时间复杂度为O(log n)。从数组的两端开始，通过不断取中间元素与相邻元素比较，缩小搜索范围。当左指针和右指针相遇时，左指针的位置即为峰顶索引。具体实现如下： ```cpp class Solution { public: int peakIndexInMountainArray(vector<int>& arr) { int left = 0; int right = arr.size() - 1; // 二分查找 while (left < right) { int mid = left + (right - left) / 2; // 如果中间元素小于其右侧元素，说明峰值在右边 if (arr[mid] < arr[mid + 1]) { left = mid + 1; } // 否则，峰值在左边 else { right = mid; } } // 返回左指针位置，即峰顶索引 return left; } }; ``` 在这个解决方案中，二分查找的优化在于它每次都能将搜索范围减半，对于大规模数组，这种方法能显著减少查找时间。需要注意的是，由于数组可能包含重复元素，二分查找可能无法直接找到峰顶，但可以确定峰顶所在的区间，从而找到正确的索引。