入门 对有序数组进行二分搜索 + 图解 (下篇)

4）二分搜索不一定发生在有序数组上（比如寻找峰值问题）

class Solution {
public:
    // 4）二分搜索不一定发生在有序数组上（比如寻找峰值问题）
    int findPeakElement(vector<int>& arr) {
        int n = arr.size();
        if (n == 1) return 0; 
        // 数组长度 >= 2 
        if (arr[0] > arr[1]) return 0;// 单独检查 0 位置是否为峰值，如果是就直接返回了，如果不是就继续
        if (arr[n - 1] > arr[n - 2]) return n - 1;// 单独检查 n-1 位置是否为峰值，如果是就直接返回了，如果不是就继续
        /*
            (X)       中间一定有峰值点(√)       (X)
            0                                   n-1
            中间：讨论 1~n-2 范围，一定有峰值点
            每一步的left~right：一定有峰值点
        */
        int left = 1, right = n - 2, mid = 0, ans = -1;
        while (left <= right) {
            // mid = (left + right) / 2;
            mid = left + ((right - left) >> 1);
            if (arr[mid - 1] > arr[mid]) { // 左侧(mid-1) > mid
                right = mid - 1;// 往左二分
            }
            else if (arr[mid] < arr[mid+1]) { // 右侧(mid+1) > mid
                left = mid + 1;// 往右二分
            }
            else { // mid 位置是峰值
                ans = mid;
                break;
            }
        }
        return ans;
    }
};
 

参考文章和视频：

162. 寻找峰值 - 力扣（LeetCode）https://leetcode.cn/problems/find-peak-element/solutions/998441/gong-shui-san-xie-noxiang-xin-ke-xue-xi-qva7v/算法讲解006【入门】二分搜索-左程云-算法通关-哔哩哔哩视频 (bilibili.com)https://www.bilibili.com/list/8888480?sid=3509640&spm_id_from=333.999.0.0&desc=1&oid=359276770&bvid=BV1bX4y177uT

 参考牛客的官文题解：寻找峰值_牛客题霸_牛客网 (nowcoder.com)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findPeakElement(vector<int>& nums) {
        int left = 0,right = nums.size()-1;
        // 二分法
        while(left < right) {
            int mid = left + ((right-left)>>1);
            // 右边是往下，不一定有波峰
            if(nums[mid] > nums[mid+1]) {
                right = mid;
            }
            // 右边是往上，一定能找到波峰
            else {
                left = mid+1;
            }
        }
        // 其中一个波峰
        return right;
    }
};
 
 
/*
// 右边往下，不一定有波峰
if(nums[mid] > nums[mid+1]) {
    right = mid;
}
//右边是往上，一定能找到波峰
else {
    left = mid+1;
}
*/