1. 理解山脉数组与峰值索引
一个数组 arr 被定义为山脉数组，需满足以下条件：
- arr.length >= 3
- 存在一个索引 i（0
- arr[0]
- arr[i] > arr[i+1] > ... > arr[arr.length-1] (严格递减)
我们的目标是找到这个峰值 arr[i] 对应的索引 i。例如，对于数组 [0, 2, 1, 0]，峰值是 2，其索引为 1。问题的核心挑战在于，要求算法的时间复杂度必须为 O(log(arr.length))。
2. O(log N) 复杂度要求下的二分查找
由于问题明确要求 O(log N) 的时间复杂度，这意味着我们需要采用二分查找（Binary Search）策略。二分查找适用于在有序或具有某种单调性的数据结构中进行搜索。山脉数组虽然整体无序，但在峰值两侧分别呈现严格的单调性（递增和递减），这为二分查找提供了可能。
2.1 初始尝试的常见问题分析
在实现二分查找时，常见的错误在于对边界条件和搜索方向的判断。例如，一个常见的错误实现可能如下：
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int low = 0;
int high = arr.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
// 错误的判断逻辑和边界处理
if (mid == 0 || (arr[mid] >= arr[mid - 1]) && (mid == high || arr[mid] >= arr[mid + 1]))
return mid;
else if (mid > 0 || arr[mid - 1] > arr[mid]) { // 这里的条件和逻辑更新是错误的
low = mid + 1;
}
high = mid - 1; // 这里的 high 更新不应是无条件的
}
return mid;
}
}上述代码的问题在于：
- 条件判断不准确：mid==0 或 mid==high 时的边界处理复杂且容易出错。
- 逻辑运算符误用：| (位或) 在这里应使用 || (逻辑或)。
- 搜索空间更新错误：else if 和 high = mid - 1 的更新逻辑会导致搜索方向混乱，无法正确收敛到峰值。特别是在 arr[mid-1] > arr[mid] 时，意味着当前在递减坡上，峰值应在左侧或当前位置，但却将 low 移到 mid+1，导致峰值被跳过。
2.2 正确的二分查找策略
实现 O(log N) 的二分查找，关键在于根据 arr[mid] 与其相邻元素 arr[mid+1] 的关系来判断峰值可能存在的区间：
-
初始化搜索区间：
- low = 0
- high = arr.length - 1
- 由于峰值 i 满足 0
-
循环条件：
- while (low
-
计算中间索引：
- mid = low + (high - low) / 2：这种写法可以有效避免 (low + high) 溢出。
-
判断峰值位置并更新搜索区间：
- 情况一：arr[mid]
- 这意味着 mid 位于山脉的上升坡上。峰值一定在 mid 的右侧（包括 mid+1）。
- 因此，将搜索区间的下限 low 更新为 mid + 1。
-
情况二：arr[mid] > arr[mid+1]
- 这意味着 mid 位于山脉的下降坡上，或者 mid 本身就是峰值。峰值可能在 mid 处或 mid 的左侧。
- 因此，将搜索区间的上限 high 更新为 mid。
- 情况一：arr[mid]
-
返回结果：
- 当循环结束时 (low == high)，low (或 high) 所指向的索引就是峰值索引。
3. Java 代码实现 (O(log N))
public class Solution {
/**
* 在山脉数组中查找峰值索引，时间复杂度为 O(log N)。
*
* @param arr 山脉数组
* @return 峰值索引
*/
public int peakIndexInMountainArray(int[] arr) {
int low = 0;
// 搜索区间可以设定为 [0, arr.length - 1]
// 也可以更精确地设定为 [1, arr.length - 2]，因为峰值不可能在两端
int high = arr.length - 1;
// 当 low == high 时，循环结束，此时 low (或 high) 就是峰值索引
while (low < high) {
int mid = low + (high - low) / 2;
// 如果 arr[mid] 小于 arr[mid+1]，说明 mid 在上升坡
// 峰值在 mid 的右侧，更新 low
if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
}
// 如果 arr[mid] 大于 arr[mid+1]，说明 mid 在下降坡或 mid 就是峰值
// 峰值在 mid 或 mid 的左侧，更新 high
else { // arr[mid] > arr[mid+1]
high = mid;
}
}
// 循环结束时，low 和 high 相等，指向峰值索引
return low;
}
public static void main(String[] args) {
Solution solver = new Solution();
System.out.println("Set 1: [0,1,2] -> Peak Index: " + solver.peakIndexInMountainArray(new int[]{0,1,2})); // 2
System.out.println("Set 2: [0,1,0] -> Peak Index: " + solver.peakIndexInMountainArray(new int[]{0,1,0})); // 1
System.out.println("Set 3: [0,2,1,0] -> Peak Index: " + solver.peakIndexInMountainArray(new int[]{0,2,1,0})); // 1
System.out.println("Set 4: [0,10,5,2] -> Peak Index: " + solver.peakIndexInMountainArray(new int[]{0,10,5,2})); // 1
System.out.println("Set 5: [0,100,500,2] -> Peak Index: " + solver.peakIndexInMountainArray(new int[]{0,100,500,2})); // 2
}
}4. O(N) 线性扫描解法（作为对比）
尽管问题要求 O(log N)，但如果忽略时间复杂度要求，最直观且简单的解法是进行一次线性扫描。这种方法通过遍历数组，维护当前遇到的最大值及其索引，最终找到峰值。
public class LinearScanSolution {
/**
* 在山脉数组中查找峰值索引，时间复杂度为 O(N)。
*
* @param arr 山脉数组
* @return 峰值索引
*/
public static int peakIndexInMountainArray(int[] arr) {
int peakValue = arr[0]; // 假设第一个元素是初始峰值
int peakIndex = 0;
for (int i = 1; i < arr.length; i++) { // 从第二个元素开始遍历
int value = arr[i];
if (value > peakValue) {
peakValue = value;
peakIndex = i;
} else {
// 如果当前值不大于peakValue，且之前是递增，现在开始递减，
// 那么当前的peakValue就是峰值。
// 由于山脉数组的特性，一旦开始下降，就不会再上升，
// 所以可以直接返回当前的 peakIndex。
// 优化：对于山脉数组，一旦遇到下降趋势，就可以确定峰值已过
return peakIndex;
}
}
return peakIndex; // 适用于数组只有递增部分（不严格的山脉）或递增到末尾的情况
}
public static void main(String[] args) {
System.out.println("Set 1: " + peakIndexInMountainArray(new int[]{0,1,2})); // 2
System.out.println("Set 2: " + peakIndexInMountainArray(new int[]{0,1,0})); // 1
System.out.println("Set 3: " + peakIndexInMountainArray(new int[]{0,2,1,0})); // 1
System.out.println("Set 4: " + peakIndexInMountainArray(new int[]{0,10,5,2})); // 1
System.out.println("Set 5: " + peakIndexInMountainArray(new int[]{0,100,500,2})); // 2
}
}注意事项：
- 上述线性扫描代码中的优化 return peakIndex; 仅适用于严格的山脉数组定义。如果 arr[i] 不大于 peakValue，且 arr[i-1] 已经小于 arr[i] (即在递增段)，这说明 arr[i-1] 才是峰值。但由于 peakValue 已经记录了 arr[i-1]，所以直接返回 peakIndex 是正确的。
- 虽然此方法功能上正确，但其时间复杂度为 O(N)，不符合原问题 O(log N) 的要求。因此，在有严格复杂度要求的场景下，应优先选择二分查找。
5. 总结与注意事项
- 理解问题定义：在解决任何算法问题之前，务必仔细阅读并理解所有约束条件，特别是时间复杂度要求。
- 二分查找的核心：在于每次迭代都能将搜索空间减半。对于山脉数组，通过比较 arr[mid] 和 arr[mid+1]，可以确定峰值位于 mid 的左侧或右侧，从而正确收缩搜索区间。
- 边界处理：在二分查找中，low
- 溢出风险：计算 mid 时使用 low + (high - low) / 2 优于 (low + high) / 2，以防止 low + high 发生整数溢出。
- O(N) 与 O(log N)：虽然线性扫描更直观易懂，但在大数据量下，O(log N) 的二分查找具有显著的性能优势。对于本问题，应优先采用二分查找。
