问题回顾

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

思路：通过二分查找寻找峰值元素，关键在于利用局部单调性决定搜索方向。

---

核心思路

1. 峰值的存在性：题目保证相邻元素不同，且两端视为负无穷，因此至少存在一个峰值。
2. 局部单调性判断：
   • 若 nums[mid] > nums[mid-1]，说明右侧可能存在更高点（上升趋势），向右搜索。
   • 若 nums[mid] <= nums[mid-1]，说明左侧可能存在更高点（下降趋势），向左搜索。

---

代码逻辑分析

int findPeakElement(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return 0;
    if (nums[0] > nums[1]) return 0;       // 首元素可能是峰值
    if (nums[n-1] > nums[n-2]) return n-1; // 尾元素可能是峰值
    int l = 1, r = n-2; // 排除首尾，缩小搜索范围
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {
            return mid; // 找到峰值
        } else if (nums[mid] > nums[mid-1]) {
            l = mid + 1; // 右侧可能存在更高点
        } else {
            r = mid - 1; // 左侧可能存在更高点
        }
    }
    return r; // 最终 l == r，返回任意一个
}

---

为什么 l = mid + 1 和 r = mid - 1 不可互换？

1. 方向依赖局部单调性

• 当 nums[mid] > nums[mid-1]
  当前处于上升趋势，右侧可能有更高点（例如 [1,3,2]，mid=1 时右侧存在峰值）。

  • 正确操作：l = mid + 1（向右搜索）。
  • 错误操作：若互换为 r = mid - 1，会错过右侧的峰值。

• 当 nums[mid] <= nums[mid-1]
  当前处于下降趋势，左侧可能有更高点（例如 [3,2,1]，mid=1 时左侧存在峰值）。

  • 正确操作：r = mid - 1（向左搜索）。
  • 错误操作：若互换为 l = mid + 1，会错过左侧的峰值。

2. 数学证明

• 定理：在非严格单调递增/递减的区间中，峰值一定存在于更高的一侧。
• 反证法：若操作方向错误，会导致搜索区间跳过所有可能的峰值。

3. 示例验证

• 示例1：nums = [1,2,3,1]

  • 初始 l=1, r=2，mid=1（值为2）。
  • nums[mid] > nums[mid-1] → 向右搜索 l=2。
  • 最终 l=r=2，返回正确索引2。

• 若互换操作：

  • nums[mid] > nums[mid-1] → 错误向左搜索 r=0，区间变为 [1,0]，直接返回0，结果错误。

---

边界条件处理

1. 数组长度为1：直接返回0。
2. 首尾元素检查：若首元素大于次元素，或尾元素大于前元素，直接返回。
3. 循环终止条件：l < r 保证最终收敛到 l == r，此时剩余元素即为峰值。

---

时间复杂度

• 每次将搜索范围减半，时间复杂度为 O(log n)，符合题目要求。

---

总结

代码通过分析局部单调性，动态调整搜索方向，确保每次缩小范围时保留可能的峰值区域。l = mid + 1 和 r = mid - 1 的方向选择是算法的核心逻辑，不可互换，否则会破坏搜索方向的正确性。