LC162.寻找峰值

原题链接

思路

• 此题极好的体现了“二分查找的关键在于二段性，而不是有序性”
• 如果nums[i] < nums[i + 1]，说明峰值必不可能在左边，因此放弃掉左边（left = mid + 1）,因此本题的二段性体现在“峰值必不可能在哪一侧”。
• 二分的细节处理
  1. 如果向上取整 ```cpp int mid = (left + right + 1) / 2;

如果放弃掉左边

left = mid;

如果放弃掉右边

right = mid - 1;

判断趋势

if (nums[i - 1] < nums[i]);

错误的写法:向上取整禁止出现 + 1

if (nums[i] < nums[i + 1]);

   2. 如果向下取整
```cpp
int mid = (left + right) / 2;
# 如果放弃左边
left = mid + 1;
# 如果放弃右边
right = mid;
# 判断趋势
if (nums[i - 1] < nums[i]);
# 错误的写法：向下取整禁止出现 - 1
if (nums[i] < nums[i + 1]

代码

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int len = nums.size();
        if (!len || len == 1) return 0;
        // 方法一：
        int l = 0, r = len - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            // nums[mid + 1]可能会爆掉
            if (nums[mid - 1] <= nums[mid]) {
                // 放弃掉左边
                l = mid;
            } else {
                // 放弃掉右边
                r = mid - 1;
            }
        }
        // 方法二：
        /*
        int l = 0, r = len - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] < nums[mid + 1]) {
                // 放弃掉左边
                l = mid + 1;
            } else {
                // 放弃掉右边
                r = mid;
            }
        }
        */
        return l;
    }
};