1. 引言：理解山脉数组与峰值问题
在计算机科学中，"山脉数组"（mountain array）是一种特殊的数组结构，它具有以下明确的特性：
- 数组的长度至少为3。
- 存在一个索引 i（0 arr[i+1] > ... > arr[arr.length-1]。
我们的目标是找到这个唯一的峰值索引 i。特别地，问题要求解决方案的时间复杂度必须达到 O(log(arr.length))，这强烈暗示我们需要采用二分查找（Binary Search）策略。
2. 初始二分查找尝试及问题诊断
许多开发者在面对 O(logN) 复杂度要求时，会自然想到二分查找。然而，二分查找的实现细节，尤其是在非简单查找场景下，常常容易出错。以下是一个常见的、存在问题的二分查找尝试：
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;
// 尝试判断 mid 是否为峰值，但条件过于复杂且不准确
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; // 此行无条件执行，导致逻辑混乱
}
return mid;
}
}问题诊断：
- 峰值判断条件复杂且不准确： mid==0 或 mid==high 不可能是峰值，因为山脉数组定义要求峰值 i 满足 0 = arr[mid-1] 和 arr[mid] >= arr[mid+1] 的组合判断，在边界处理和逻辑上容易出错，未能充分利用山脉数组的单调性。
- 搜索区间更新策略混乱： else if (mid > 0 || arr[mid-1] > arr[mid]) 的条件并不明确指向峰值在左侧还是右侧。更严重的是，high = mid - 1; 语句在 else if 块外部无条件执行，这意味着无论 mid 是在上升坡还是下降坡，high 都会被错误地向左移动，导致搜索范围收缩不正确，甚至错过峰值。
- 循环条件与返回值的配合： while(low
3. 线性扫描方法：简单但非最优
在某些情况下，一个简单直观的线性扫描（Linear Scan）方法也能找到峰值。这种方法遍历整个数组，记录当前遇到的最大值及其索引。由于山脉数组的特性，数组中的最大值必然是峰值。
public class Solution {
public static int peakIndexInMountainArray(int[] arr) {
int peakValue = 0; // 初始值应根据实际数据范围调整，或使用arr[0]
int peakIndex = 0;
for (int i = 0; i < arr.length; i++) {
int value = arr[i];
if (value > peakValue) {
peakValue = value;
peakIndex = i;
}
}
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
}
}分析：
- 工作原理： 此方法通过简单遍历数组，比较每个元素与当前记录的 peakValue，若当前元素更大，则更新 peakValue 和 peakIndex。对于山脉数组而言，其最大值就是峰值，因此此方法能正确找到峰值索引。
- 局限性： 尽管它能得到正确结果，但其时间复杂度为 O(N)，其中 N 是数组的长度。这不符合题目中明确要求的 O(log(arr.length)) 复杂度。对于大规模数组，线性扫描的效率远低于二分查找。
4. 最优解：基于二分查找的峰值定位
要满足 O(logN) 的时间复杂度，我们必须采用二分查找。关键在于如何根据 mid 位置的元素，正确地缩小搜索区间。
核心思想：
利用山脉数组的单调性，我们可以通过比较 arr[mid] 和 arr[mid+1] 来判断 mid 位于上升坡还是下降坡，从而确定峰值的大致方向。
- 如果 arr[mid] 这意味着 mid 位于山脉的上升坡上。因为数组是严格递增的，mid 肯定不是峰值，峰值一定在 mid 的右侧。因此，我们将搜索范围的下界 low 更新为 mid + 1。
- 如果 arr[mid] > arr[mid+1]： 这意味着 mid 位于山脉的下降坡上，或者 mid 本身就是峰值。在这种情况下，峰值可能就是 mid，也可能在 mid 的左侧。因此，我们将搜索范围的上界 high 更新为 mid。
算法步骤：
- 初始化 low = 0 和 high = arr.length - 1，定义完整的搜索区间。
- 使用 while (low
- 在循环内部，计算 mid = low + (high - low) / 2，以防止整数溢出（相比 (low + high) / 2 更安全）。
- 根据 arr[mid] 与 arr[mid+1] 的比较结果更新 low 或 high：
- 如果 arr[mid]
- 如果 arr[mid] > arr[mid+1]，则 high = mid。
- 当循环结束时，low（或 high）的值即为山脉数组的峰值索引。
示例代码：
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int low = 0;
// 搜索范围可以覆盖整个数组。
// 因为题目保证了峰值不在两端，所以实际峰值会在 [1, arr.length - 2] 区间内。
// 但为了通用性，我们通常将 high 初始化为 arr.length - 1。
int high = arr.length - 1;
// 循环条件：当 low == high 时，表示找到了峰值索引
while (low < high) {
int mid = low + (high - low) / 2; // 计算中间索引，防止溢出
// 如果 mid 位于上升坡 (arr[mid] < arr[mid+1])
// 峰值一定在 mid 的右侧，mid 肯定不是峰值
if (arr[mid] < arr[mid + 1]) {
low = mid + 1;
}
// 如果 mid 位于下降坡 (arr[mid] > arr[mid+1])
// 或者 mid 就是峰值
// 峰值可能就是 mid，也可能在 mid 的左侧 
