Find Peak Element

162. 寻找峰值

分析

定义区间：
- 使用两个指针 l 和 r，分别指向数组的起点和终点，表示当前搜索的范围
二分查找：
- 计算中间位置 mid = (l + r) / 2
- 比较 nums[mid] 和 nums[mid + 1] ：
  - 如果 nums[mid] > nums[mid + 1] ：说明峰值可能在左侧（包括当前 mid），将右边界 r 移到 mid
  - 如果 nums[mid] < nums[mid + 1] ：说明峰值可能在右侧，更新左边界 l 为 mid + 1
结束条件：
- 当 l == r 时，区间缩小为一个位置，此时该位置即为峰值索引

时间复杂度

时间复杂度 O(logn)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution
{
public:
    int findPeakElement(vector<int>& nums)
    {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > nums[mid + 1])
                r = mid; // 峰值在左侧或当前 mid
            else
                l = mid + 1; // 峰值在右侧
        }
        return r; // 或返回 l，最终 l == r
    }
};