二分搜索的三种方法

server/2024/11/16 23:56:54/

首先总的说一下二分搜索。如果区间具有二分性,这个二分性不仅仅是指区间是有序的,而是我们可以通过某一种性质将整个区间分成左区间和右区间。我们通过二分的方法去不断缩小查找的区间,最终让区间内没有元素,这个时候的我们就得到了分界的边界。

二分问题的难点在于边界的处理,整不好就死循环了,所以我们面对二分问题要一步一步分析,不要漏掉东西。

这里有两个原则大家要记住:

1)我们的最终目的就是让搜索区间没有一个元素;

2)left 的左面全都是<target的,right 的右面全都是>=target的(注意,这里的<,>=不是一定的,根据我们自己定的条件为主)。

这两个在这里不懂没关系,继续往下看就明白了。

一.全闭区间

即我们的查找区间的闭区间的,这个选择也影响到了我们的循环终止条件。我们的最终目的就是让区间没有一个元素,两面都是闭的,我们必须要 l<=r 。为什么?闭区间要想没有元素,要让 l 与 r 错开才行。

//闭区间
int n=nums.length;
int left=0;
int right=n-1;while(left<=right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else{right=mid-1;}
}

可能有的问题:

1.left和right的初始值为什么是这个?

left和right的初始值是根据我们区间的开闭写的。如果左面是开区间,left=-1,闭区间,left=0;右面同理,开区间,right=n,闭区间right=n-1。

2.那我们这么写的最终left和right分别指的下标是什么?

left 的左面全都是<target的,right 的右面全都是>=target的。所以说left指的是第一个>=target的元素,right指的是最后一个<target的元素。

3.为什么left要等于mid+1,为什么不能等于mid,right也是为什么不能等于mid?

还是刚刚的那句:left 的左面全都是<target的,right 的右面全都是>=target的。比如我们已经知道了 nums[mid]<target 了,所以说mid下标的元素一定<target,left的左面都是<target的,所以left直接等于mid+1就保证了left左面全都<target。right同理。

二.半闭半开

也是大家经常在网上看到的模板的类型,本人并不推荐这种写法,+1不+1的,可能在做什么模板题的时候觉得自我良好。但是二分是一种用于优化的算法,一般不会单独出现,在一些复杂的问题其实就很乱了。

上面是一些题外话,下面才是正题。

半闭半开有两种情况:左闭右开和左开右闭。

//左闭右开
int n=nums.length;
int left=0;
int right=n;while(left<right){int mid=left+(right-left)/2;if(nums[mid]<target){left=mid+1;}else{right=mid;}
}
//左开右闭
int n=nums.length;
int left=-1;
int right=n-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]<target){left=mid;}else{right=mid-1;}
}

可能有的问题:

1.为什么上面left和right两次不同?

开的那一部分是取不到的,所以说我们就要多“往外”一点,因为一开始要全部元素都在搜索区间里。

2.为什么两种情况left和right这个+1那个-1的?

我们在上一种全闭的情况时提到:left 的左面全都是<target的,right 的右面全都是>=target的。这里就拿左闭右开举例。右面是开区间,也就是说right指向的下标的元素不在我们的搜索区间内,所以说已经满足了right 的右面全都是>=target的这个条件。我们此时说mid下标的这个元素>=target的,如果是闭区间,right要-1,但是根据开区间的性质,我们是取不到这个mid下标的元素的,可以理解成无形的减了一,我们就没必要再-1了,直接让right=mid就行了。但是left是闭的,所以要+1才能保证left 的左面全都是<target的。

左开右闭同理。

3.为什么在左开右闭时求mid要+1?

这个也是开区间影响的。在最后只剩下两个元素的时候,我们求mid,mid一定是指向左面的下标的,但是左面是开区间,也就是说左面的元素不在搜索区间内,不在区间怎么能判断呢?所以我们mid要+1。

4.结束时,left指向什么,right指向什么?

最终left和right会重合,所以这里说left或right都一样。

唉?为什么会重合?

因为这是一开一闭。我们最用要的是:left 的左面全都是<target的,right 的右面全都是>=target的。以左闭右开为例。比如说left和right重合的时候在t下标处,t下标对于的元素是>=target的(这是一定的),左区间是必的,所以left左面全都是<target的成立,右区间是开的,取不到t,所以right 的右面全都是>=target的。

明白上面的我们就知道left和right会指向第一个>=target的元素。

左开右闭的left和right会指向最后一个<target的元素。

5.如果区间内的元素全部<target或区间内元素全部>=target,那么left和right会指向什么?

在左必右开区间中,如果元素全部<target,我们会发现left和right会指向1,这肯定是不对的应该指向0才对。

在左开右闭,如果元素全部>=target,那么我们也会发现left和right指向错误。

这就是为什么不推荐这种写法,太乱了,我们不仅要关注加不加一,还要关注元素的问题。

三.全开区间

这是本人最推荐的一种方法,这种方法没有了+1-1的问题,方便记忆。

int n=nums.length;
int left=-1;
int right=n;while(left+1<right){int mid=left+(right-left)/2;if(nums[mid]>=target){right=mid;}else{left=mid;}
}

简洁明了。

可能有的问题:

1.循环条件为什么是left+1<right?

还是那句话:我们的最终目的就是让搜索区间没有一个元素。其实当left+1=right的时候区间内就没有一个元素了对不对,所以说这个时候就要终止了。

2.left为什么不用+1,right为什么不用-1?

大家如果看懂上面关于这方面的解释的话这个自己就明白了。一句话:因为这是全开的。

3.结束时,left指向什么,right指向什么?

left指向最后一个<target的元素,right指向第一个>=target的元素。

如果区间内的元素全部<target,那left=-1,right=0;区间内元素全部>=target,那left=n-1,right=n。

四.总结

上面加粗的问题基本上可以涵盖大家可能问到的问题,如果还有问题可以在评论区讨论。还有,上的条件>=target或<target,这都不是固定的,根据真实情况进行修改,大家理解思想就行了。一定要着重理解上面反复提到的两个原则。


http://www.ppmy.cn/server/142500.html

相关文章

SNN学习(2):深入了解SNN及LIF神经元的原理和运行过程

目录 一、STDP机制 1、STDP 的基本原理 权重调整的“时间差依赖性” 2、STDP 的数学模型 二、SNN的应用场景 三、从人工神经网络ANN到脉冲神经网络SNN 1、脉冲 2、稀疏性&#xff08;Sparsity&#xff09; 3、事件驱动处理&#xff08;静态抑制&#xff09; 四、脉冲…

【电脑】解决DiskGenius调整分区大小时报错“文件使用的簇被标记为空闲或与其它文件有交叉”

【电脑】解决DiskGenius调整分区大小时报错“文件使用的簇被标记为空闲或与其它文件有交叉” 零、报错 在使用DiskGenius对磁盘分区进行调整时&#xff0c;DiskGenius检查出磁盘报错&#xff0c;报错信息&#xff1a;文件使用的簇被标记为空闲或与其它文件有交叉&#xff0c;…

Python爬虫项目 | 一、网易云音乐热歌榜歌曲

文章目录 1.文章概要1.1 实现方法1.2 实现代码1.3 最终效果 2.具体讲解2.1 使用的Python库2.2 代码说明2.2.1 创建目录保存文件2.2.2 爬取网易云音乐热歌榜单歌曲 2.3 过程展示 3 总结 1.文章概要 学习Python爬虫知识&#xff0c;实现简单的一个小案例&#xff0c;网易云音乐热…

QInputDialog显示硕士的解决

QInputDialog 弹出卡死的原因可能有多种&#xff0c;这通常与事件循环或线程有关。以下是一些可能的解决方法&#xff1a; 确保在主线程调用对话框&#xff1a; QInputDialog 应该在主线程&#xff08;UI线程&#xff09;中运行。如果在其他线程中直接调用它&#xff0c;可能…

开源对象存储新选择:在Docker上部署MinIO并实现远程管理

文章目录 前言1. Docker 部署MinIO2. 本地访问MinIO3. Linux安装Cpolar4. 配置MinIO公网地址5. 远程访问MinIO管理界面6. 固定MinIO公网地址 前言 MinIO是一个开源的对象存储服务器&#xff0c;可以在各种环境中运行&#xff0c;例如本地、Docker容器、Kubernetes集群等。它兼…

Python学习26天

集合 # 定义集合 num {1, 2, 3, 4, 5} print(f"num&#xff1a;{num}\nnum数据类型为&#xff1a;{type(num)}") # 求集合中元素个数 print(f"num中元素个数为&#xff1a;{len(num)}") # 增加集合中的元素 num.add(6) print(num) # {1,2,3,4,5,6} # 删除…

uniapp 面试题总结常考

uniapp 文件详情 ├── pages # 页面文件夹 │ │── index # index文件夹 │ │ │── index.vue # index页面 ├── static # 静态资源&#xff08;类似于图片 字体图标等&#xff09; │ …

【软考】系统架构设计师-计算机系统基础(3):嵌入式系统

嵌入式系统&#xff1a;嵌入式处理器、相关支撑硬件、嵌入式OS、支撑软件以及应用软件 嵌入式系统特征&#xff1a;专用性强、技术融合、软硬一体软件为主、通用计算机资源少,... 分层&#xff08;5层&#xff09;&#xff1a;硬件层 → 抽象层 → 操作系统层 → 中间件层 →…