首页 > 其他分享 >二分法寻找峰值、二分法通俗易懂简单解释讲解

二分法寻找峰值、二分法通俗易懂简单解释讲解

时间:2022-10-12 16:01:27浏览次数:58  
标签:right nums int mid 通俗易懂 二分法 讲解 左闭 left

题目:BM19 寻找峰值、力扣162. 寻找峰值

public class Solution {
    /**
     * 保持在上坡的一边一定可以找到峰值,上坡只有两种情况一直为上坡,或者变为下坡
        这两种情况都符合有峰值条件,
        因为nums[-1] = nums[n] = −∞, nums[i] != nums[i + 1],所以一定可以找到
     * @param nums int整型一维数组
     * @return int整型
     */

    public int findPeakElement (int[] nums) {

        if (nums.length == 1 || nums[0] > nums[1]) return 0;
        int n = nums.length;
        if (nums[n - 1] > nums[n - 2]) return n - 1;

        int left = 0, right = nums.length - 1;

        // [left, right] 左闭右闭,left == right 有意义
        while (left <= right) {
            int mid = left + (right - left >> 1);
            // 右边为上坡 转到右半边
            if (nums[mid] < nums[mid + 1]) left = mid + 1;
            // 左边为上坡 转到左半边
            else right = mid - 1;  // 左闭右开
        }
        return left;
    }

    public int findPeakElement1 (int[] nums) {
        int left = 0, right = nums.length - 1;

        // [left, right) 左闭右开,left == right 无意义
        while (left < right) {
            int mid = left + (right - left >> 1);
            // 右边为上坡 转到右半边
            if (nums[mid] < nums[mid + 1]) left = mid + 1;
            // 左边为上坡 转到左半边
            else right = mid;  // 左闭右开
        }

        return left;
    }
}

总结:二分法什么时候用 left < right ,什么时候用 left <= right ?有什么区别。

对于二分查找来说,就是从数列的两端进行查找,更适合于对有序数列的查找操作,两端就是 left、right,其中查找途中还需要一个中间量mid表示中间值,正是这个中间值把当前数列一分为二,所以才叫二分查找。

一般情况来说,变量初始化如下:left = 0,right = nums.length - 1, mid = left + (right - left >> 1),位运算防止溢出。

情况一:使用 left < right,也就是左闭右开区间 [left, right),代码模板如下下:

    // [left, right) 左闭右开,left == right 无意义,在循环中取不到值
    while (left < right) {
        int mid = left + (right - left >> 1); 
        if (nums[mid] < target) left = mid + 1;
        // 左边为上坡 转到左半边
        else if (nums[mid] < target) right = mid;  // 左闭右开,防止mid娶不到值
        else return mid;
    }

情况二:使用 left > right,也就是左闭右闭区间 [left, right],代码模板如下下:

    // [left, right] 左闭右闭,left == right 有意义,在循环中可以娶到
    while (left <= right) {
        int mid = left + (right - left >> 1); 
        if (nums[mid] < target) left = mid + 1;
        // 左边为上坡 转到左半边
        else if (nums[mid] < target) right = mid - 1;  // 左闭右开,mid可以在循环中取到值
        else return mid;
    }

标签:right,nums,int,mid,通俗易懂,二分法,讲解,左闭,left
From: https://www.cnblogs.com/malongfeistudy/p/16784786.html

相关文章