您好,欢迎来到化拓教育网。
搜索
您的当前位置:首页手撕二分法查找(边界值注意点)

手撕二分法查找(边界值注意点)

来源:化拓教育网

前文介绍

  二分法查找相信很多同学都是一看就会,一做就废,对于一些边界的条件和left,right的取值还不是很明确,那你看这个文章就能很好解决你的疑问了,对于完全0基础的同学,可以结合这个,来看我的文章会比较好,谢谢哈。

关于闭区间和开区间

  所谓闭区间就是区间的包括边界值,如【1,2】的正整数区间,包含1,2这两个边界值,【1,1】区间包括1这个边界值,而开区间就不会包括边界值,如(1,2),(1,1)的正整数区间,没有包含任何数,也是无效区间,为空,(1,3)这样的区间才包含了2这个数值。

二分法实战(LeetCode704题)

  理解了闭区间和开区间的概念,我们通过一道金典二分法查找算法题来实战

题目要求查找出target并返回下标,没有找到就返回返回-1,我们就分别使用左闭合右闭合区间,左闭合右开区间的二分法查找算法来解决

左闭合右闭合区间写法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
// 左右闭合区间写法
var search = function(nums, target) {
// 分别定义左右起始下标,因为是左右闭合包含边界值,
// 所以分别定义数组第一个下标和最后一个下标
    let left = 0;
    let right = nums.length-1;
// while的边界值条件判断,因为要满足while的条件才能进入循环,
// 所以区间要为有效区间,要有值,如【1,2】有1,2,【1,1】有1,
// 而【2,1】就没有值,为无效区间,所以right要大于等于left才有效
    while(left<=right){
// 取mid中间值判断
        let mid = Math.floor((left+right) / 2) 
//当mid下标对应的值大于target,说明包括mid下标和mid下标右边的值都是大于target的,
// 不是我们要的区间范围,要进行缩小(缩小的区间不包括mid),
//所以修改right(右闭合区间包括right)的值为mid-1,
// 如果right为mid,而mid下标的值是大于target的,不是我们要的范围,就不准确了
        if(nums[mid] > target){
            right = mid - 1;
//同理,当mid下标对应的值小于target,说明包括mid下标和mid下标左边的值都是小于target的,
//不是我们要的区间范围,要进行缩小(缩小的区间不包括mid),
//所以修改left(左闭合区间包括left)的值为mid+1,
//如果right为mid,而mid下标的值是小于target的,不是我们要的范围,就不准确了
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            return mid
        }
    }
    return -1;
    
};

左闭合右开区间写法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
// 左闭合右开区间写法
var search = function(nums, target) {
// 分别定义左右起始下标,因为是左闭合右开区,
// 所以左边包含边界值,右边不包含边界值
// 所以分别定义数组第一个下标和数组的长度
    let left = 0;
    let right = nums.length;
// while的边界值条件判断,因为要满足while的条件才能进入循环,
// 所以区间要为有效区间,要有值,如【1,2)有1,【1,3)有1,2
// 而【1,1),【2,1)就没有值,为无效区间,所以right要大于left(不能等于)才有效
    while(left<right){
// 取mid中间值判断
        let mid = Math.floor((left+right) / 2) 
//当mid下标对应的值大于target,说明包括mid下标和mid下标右边的值都是大于target的,
// 不是我们要的区间范围,要进行缩小(缩小的区间不包括mid),
//所以修改right(右开区间是不包括right)的值mid,
// 如果right为mid-1,而mid-1下标的值是我们进行缩小的区间范围,但不包括(右开区间),所以是不对的
        if(nums[mid] > target){
            right = mid;
//同理,当mid下标对应的值小于target,说明包括mid下标和mid下标左边的值都是小于target的,
//不是我们要的区间范围,要进行缩小(缩小的区间不包括mid),
//所以修改left(左闭合区间包括left)的值为mid+1,
//如果right为mid,而mid下标的值是小于target的,不是我们要的范围,就不准确了
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            return mid
        }
    }
    return -1;
    
};

以上就是二分法查找中容易有问题的边界值取值问题,包括left,right的取值,while的循环条件,right和left与mid的关系,同学们也可以跳转看视频学习,谢谢大家

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- huatuo9.cn 版权所有 赣ICP备2023008801号-1

违法及侵权请联系:TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务