前文介绍
二分法查找相信很多同学都是一看就会,一做就废,对于一些边界的条件和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的关系,同学们也可以跳转看视频学习,谢谢大家