1. 山脉数组及其特性
一个数组 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] (严格递减)
简而言之，山脉数组形如“先上升后下降”的山峰状，其峰值是数组中唯一的最大元素。例如，[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)
public class Solution {
public static int peakIndexInMountainArrayLinear(int[] arr) {
int peakValue = arr[0]; // 初始峰值设为第一个元素
int peakIndex = 0;
// 从第二个元素开始遍历，因为第一个元素不可能是峰值（除非数组长度小于3，但山脉数组定义排除此情况）
// 实际上，从arr[0]开始遍历也可以，只要确保peakValue和peakIndex的初始值正确
for (int i = 1; i < arr.length; i++) {
if (arr[i] > peakValue) {
peakValue = arr[i];
peakIndex = i;
} else {
// 一旦遇到下降趋势，说明峰值已经找到，因为山脉数组只有一个峰值
// 进一步优化，可以提前退出循环
break;
}
}
return peakIndex;
}
public static void main(String[] args) {
System.out.println("Set 1: " + peakIndexInMountainArrayLinear(new int[]{0,1,2})); // 2
System.out.println("Set 2: " + peakIndexInMountainArrayLinear(new int[]{0,1,0})); // 1
System.out.println("Set 3: " + peakIndexInMountainArrayLinear(new int[]{0,2,1,0})); // 1
System.out.println("Set 4: " + peakIndexInMountainArrayLinear(new int[]{0,10,5,2})); // 1
System.out.println("Set 5: " + peakIndexInMountainArrayLinear(new int[]{0,100,500,2})); // 2
}
}2.3 复杂度分析
- 时间复杂度： O(N)，其中 N 是数组的长度。在最坏情况下（峰值在数组末尾），需要遍历整个数组。
- 空间复杂度： O(1)，只使用了常数额外的空间。
虽然此方法简单有效，但它不满足 O(log(arr.length)) 的时间复杂度要求。
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 中也存在问题。
通过对比线性扫描和二分查找两种方法，我们可以清楚地看到，在满足特定条件（如山脉数组的单调性）时，二分查找能够显著提升算法效率，将时间复杂度从线性降低到对数级别，这对于处理大规模数据集至关重要。理解并正确应用二分查找是解决此类优化问题的关键。
