算法-没有bug的二分查找
科普:
第一篇二分搜索论文是 1946 年发表,然而第一个没有 bug 的二分查找法却是在 1962 年才出现,中间用了 16 年的时间。
定义
在计算机科学中,二分查找(英语:binary search),也称折半搜索(英语:half-interval search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。
算法
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束。如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
如果让你写二分查找你可能会这么写:
public static int find(int[] a,int data) {
int mid = 0;
if(a!=null) {
int min=0;
int max=a.length;
while(min<=max) {
mid=(min+max)/2;
if(data>a[mid]) {
min=mid+1;
}else if(data<a[mid]){
max=mid-1;
}else {
return mid;
}
}
return -1;
}else {
return -1;
}
}
上述代码哪里可能会出现bug?
答案是 mid=(min+max)/2;
原因是当min和max的值太大时可能会导致溢出,导致数组访问出错。
那么这么改进呢?一般做法是将加法变成减法,
public static int find(int[] a,int data) {
int mid = 0;
if(a!=null) {
int min=0;
int max=a.length;
while(min<=max) {
mid=min+(max-min)/2;
if(data>a[mid]) {
min=mid+1;
}else if(data<a[mid]){
max=mid-1;
}else {
return mid;
}
}
return -1;
}else {
return -1;
}
}
min+(max-min)/2和(min+max)/2是等价的,但是min+(max-min)/2在计算过程中最大数值不会超过max
还有一种更高逼格的写法,也是官方二分搜索算法的实现:位运算
public static int find(int[] a,int data) {
int mid = 0;
if(a!=null) {
int min=0;
int max=a.length;
while(min<=max) {
mid=min+((max-min)>>>1);//无符号位运算的优先级较低
if(data>a[mid]) {
min=mid+1;
}else if(data<a[mid]){
max=mid-1;
}else {
return mid;
}
}
return -1;
}else {
return -1;
}
}
评论区
请写下您的评论...
猜你喜欢
blog
没有bug的二分查找-递归写法
数据结构与算法
3980
题目:在一个有序数组中查找指定的数,如果存在返回其数组下标,否则返回-1packagetest;/*** 二分查找*@author硅谷探秘者(jia)*/publicclassTestMain2
blog
并查集 算法分析
数据结构,算法基础
766
理一些不交集(DisjointSets)的合并及查询问题。有一个联合-查找算法(union-findalgorithm)定义了两个用于此数据结构的操作:
Find:确定元素属于哪一个子集。它可以被用
其他
5806
1.没有vim命令2.使用apt-get命令安装命令如下:apt-getinstallvim3.执行过程可能会报错如下:1.如果进入容器时没有指定root用户,则可能会报错
weblog
10372
什么是floyd算法在计算机科学中,Floyd-Warshall算法是一种在具有正或负边缘权重(但没有负周期)的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度(加权
blog
算法-求和问题
数据结构与算法
12595
(returnnewint[]={1,2}),如果没有返回-1(returnnewint[]={-1,-1})。算法:用查找表解决问题实现:packageclub.test;importjava.util.HashMap;im
ofc
二叉树的所有路径
official
1190
径。说明:叶子节点是指没有子节点的节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所有根节点到叶子节点的路径为:1-2-5,1-3解题思路递归得方式遍历二叉树(深度优先搜索),
blog
算法-数的分解
数据结构与算法
6857
题目描述思路:枚举,只需要枚举前两个数,满足条件的第三个数自然是2019减去前两个数。代码packagelanqiao;publicclassTestMain1
blog
数据结构-算法-完全二叉树的权值
数据结构与算法
5886
试题描述:思路:用数组表示完全二叉树,用先序遍历的方式遍历每一层的节点,用一个数组储存每一层的和,因为数据规模小于100000所以用一个容量为17的数组即可。计算完每一层的和,再比较层数最小之和最大
最新发表
归档
2018-11
12
2018-12
33
2019-01
28
2019-02
28
2019-03
32
2019-04
27
2019-05
33
2019-06
6
2019-07
12
2019-08
12
2019-09
21
2019-10
8
2019-11
15
2019-12
25
2020-01
9
2020-02
5
2020-03
16
2020-04
4
2020-06
1
2020-07
7
2020-08
13
2020-09
9
2020-10
5
2020-12
3
2021-01
1
2021-02
5
2021-03
7
2021-04
4
2021-05
4
2021-06
1
2021-07
7
2021-08
2
2021-09
8
2021-10
9
2021-11
16
2021-12
14
2022-01
7
2022-05
1
2022-08
3
2022-09
2
2022-10
2
2022-12
5
2023-01
3
2023-02
1
2023-03
4
2023-04
2
2023-06
3
2023-07
4
2023-08
1
2023-10
1
2024-02
1
2024-03
1
2024-04
1
2024-08
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
mysql
ensp
网络基础
xxl-job
rabbitmq
haproxy
srs
音视频
webrtc
javascript
加密算法
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。