本文旨在探讨如何在山脉数组中高效地找到其峰值索引。我们将首先介绍山脉数组的定义，然后分析一种直观的线性扫描方法及其局限性。随后，重点讲解如何利用二分查找算法，在对数时间复杂度内准确地定位峰值，并提供详细的代码实现和注意事项，以满足严格的性能要求。
1. 山脉数组及其特性
一个数组 arr 被称为山脉数组，需满足以下条件：
arr.length >= 3存在一个索引 i（0 < i < arr.length – 1），使得：arr[0] < arr[1] < … < arr[i-1] arr[i+1] > … > arr[arr.length – 1] (严格递减)
简而言之，山脉数组形如“先上升后下降”的山峰状，其峰值是数组中唯一的最大元素。例如，[0, 2, 1, 0] 是一个山脉数组，其峰值索引为 1，对应的值是 2。
2. 线性扫描方法
最直观的解决方案是遍历整个数组，找到最大值及其对应的索引。由于山脉数组的特性，最大值必然是唯一的峰值。
2.1 算法思路
初始化 peakValue 为 arr[0]，peakIndex 为 0。从数组的第二个元素开始遍历。如果当前元素 arr[i] 大于 peakValue，则更新 peakValue = arr[i]，peakIndex = i。遍历结束后，peakIndex 即为峰值索引。
2.2 示例代码 (Java)
%ignore_pre_1%2.3 复杂度分析
时间复杂度： O(N)，其中 N 是数组的长度。在最坏情况下（峰值在数组末尾），需要遍历整个数组。空间复杂度： O(1)，只使用了常数额外的空间。
虽然此方法简单有效，但它不满足 O(log(arr.length)) 的时间复杂度要求。
MacsMind
电商AI超级智能客服
141 查看详情
3. 基于二分查找的优化方法
为了达到 O(logN) 的时间复杂度，我们必须利用二分查找。山脉数组的特性（先递增后递减）使得二分查找成为可能。
3.1 算法思路
二分查找的核心在于每次迭代都能排除掉一半的搜索空间。在山脉数组中，我们可以通过比较中间元素 arr[mid] 与其右侧元素 arr[mid+1] 来判断当前 mid 所在的位置：
初始化搜索范围： low = 0, high = arr.length – 1。由于峰值不会在数组的两端（0 < i < arr.length – 1），可以将 low 初始化为 1，high 初始化为 arr.length – 2，但为了通用性，使用 0 和 arr.length – 1 更安全，并在循环条件中处理边界。循环条件： while (low < high)。当 low == high 时，循环结束，low (或 high) 即为峰值索引。计算中间索引： mid = low + (high – low) / 2。判断 arr[mid] 的位置：如果 arr[mid] < arr[mid+1]： 这意味着 mid 位于山脉的上升坡上。峰值一定在 mid 的右侧（包括 mid+1）。因此，将 low 更新为 mid + 1。如果 arr[mid] > arr[mid+1]： 这意味着 mid 位于山脉的下降坡上，或者 mid 本身就是峰值。峰值可能在 mid 处，也可能在 mid 的左侧。因此，将 high 更新为 mid。
3.2 示例代码 (Java)
public class Solution { public int peakIndexInMountainArrayBinarySearch(int[] arr) { int low = 0; int high = arr.length - 1; // 循环条件是 low < high，当 low == high 时，表示找到了峰值索引 while (low < high) { int mid = low + (high - low) / 2; // 防止溢出 // 比较 arr[mid] 和 arr[mid+1] if (arr[mid] < arr[mid + 1]) { // 如果 arr[mid] 小于 arr[mid+1]，说明当前在上升坡 // 峰值在 mid 的右侧，包括 mid+1 low = mid + 1; } else { // 如果 arr[mid] 大于 arr[mid+1]，说明当前在下降坡或者 mid 就是峰值 // 峰值可能在 mid，也可能在 mid 的左侧 high = mid; } } // 循环结束时，low == high，这个索引就是峰值 return low; } public static void main(String[] args) { Solution sol = new Solution(); System.out.println("Set 1 (Binary Search): " + sol.peakIndexInMountainArrayBinarySearch(new int[]{0,1,2})); // 2 System.out.println("Set 2 (Binary Search): " + sol.peakIndexInMountainArrayBinarySearch(new int[]{0,1,0})); // 1 System.out.println("Set 3 (Binary Search): " + sol.peakIndexInMountainArrayBinarySearch(new int[]{0,2,1,0})); // 1 System.out.println("Set 4 (Binary Search): " + sol.peakIndexInMountainArrayBinarySearch(new int[]{0,10,5,2})); // 1 System.out.println("Set 5 (Binary Search): " + sol.peakIndexInMountainArrayBinarySearch(new int[]{0,100,500,2})); // 2 }}
3.3 复杂度分析
时间复杂度： O(logN)，每次迭代都将搜索空间减半。空间复杂度： O(1)，只使用了常数额外的空间。
4. 注意事项与总结
数组长度： 题目明确规定山脉数组长度 arr.length >= 3，且峰值索引 i 满足 0 < i < arr.length – 1。这意味着峰值不会是数组的第一个或最后一个元素，这简化了二分查找的边界处理。二分查找的边界条件： 在二分查找中，mid = low + (high – low) / 2 可以有效避免 (low + high) 溢出。while (low < high) 循环条件以及 high = mid 和 low = mid + 1 的更新策略是处理这种类型问题的标准做法，确保最终 low 指向正确的结果。错误代码分析： 原始问题中提供的错误代码尝试使用二分查找，但其条件判断 if (mid==0 | (arr[mid]>=arr[mid-1]) && (mid==high | arr[mid]>=arr[mid+1])) 过于复杂且存在逻辑错误，未能正确区分上升、下降和峰值情况，导致搜索空间无法正确收敛。例如，mid==0 或 mid==high 的边界条件判断与核心逻辑混淆，且 mid>0 | arr[mid-1]>arr[mid] 这样的逻辑在 else if 中也存在问题。
通过对比线性扫描和二分查找两种方法，我们可以清楚地看到，在满足特定条件（如山脉数组的单调性）时，二分查找能够显著提升算法效率，将时间复杂度从线性降低到对数级别，这对于处理大规模数据集至关重要。理解并正确应用二分查找是解决此类优化问题的关键。
以上就是求解山脉数组的峰值索引：从线性扫描到二分查找的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/771654.html
微信扫一扫 
支付宝扫一扫 
