算法-没有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的二分查找-递归写法
数据结构与算法
3133
题目:在一个有序数组中查找指定的数,如果存在返回其数组下标,否则返回-1packagetest;/*** 二分查找*@author硅谷探秘者(jia)*/publicclassTestMain2
其他
3448
1.没有vim命令2.使用apt-get命令安装命令如下:apt-getinstallvim3.执行过程可能会报错如下:1.如果进入容器时没有指定root用户,则可能会报错
weblog
9352
什么是floyd算法在计算机科学中,Floyd-Warshall算法是一种在具有正或负边缘权重(但没有负周期)的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度(加权
blog
算法-求和问题
数据结构与算法
11703
(returnnewint[]={1,2}),如果没有返回-1(returnnewint[]={-1,-1})。算法:用查找表解决问题实现:packageclub.test;importjava.util.HashMap;im
ofc
二叉树的所有路径
official
423
径。说明:叶子节点是指没有子节点的节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所有根节点到叶子节点的路径为:1-2-5,1-3解题思路递归得方式遍历二叉树(深度优先搜索),
blog
算法-数的分解
数据结构与算法
5996
题目描述思路:枚举,只需要枚举前两个数,满足条件的第三个数自然是2019减去前两个数。代码packagelanqiao;publicclassTestMain1
blog
数据结构-算法-完全二叉树的权值
数据结构与算法
4976
试题描述:思路:用数组表示完全二叉树,用先序遍历的方式遍历每一层的节点,用一个数组储存每一层的和,因为数据规模小于100000所以用一个容量为17的数组即可。计算完每一层的和,再比较层数最小之和最大
weblog
3793
种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发
最近发表
归档
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月
1
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
消息中间件
搜索
maven
redis
docker
dubbo
vue
导入导出
软件使用
idea插件
协议
无聊的知识
jenkins
springboot
mqtt协议
keepalived
minio
目录
祝愿神州十三飞行乘组平安归来