算法-没有bug的二分查找

硅谷探秘者 5601 0 0

科普:

        第一篇二分搜索论文是 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;
		}
	}


猜你喜欢
数据结构与算法 3271 题目:在一个序数组中指定数,如果存在返回其数组下标,否则返回-1packagetest;/*** *@author硅谷探秘者(jia)*/publicclassTestMain2
其他 4173 1.vim命令2.使用apt-get命令安装命令如下:apt-getinstallvim3.执行过程可能会报错如下:1.如果进入容器时指定root用户,则可能会报错
weblog 9495 什么是floyd在计机科学中,Floyd-Warshall是一种在具正或负边缘权重(但负周期)加权图中到最短路径单个执行将到所顶点对之间最短路径长度(加权
数据结构与算法 11856 (returnnewint[]={1,2}),如果返回-1(returnnewint[]={-1,-1})。:用表解决问题实现:packageclub.test;importjava.util.HashMap;im
数据结构与算法 6159 题目描述思路:枚举,只需要枚举前两个数,满足条件第三个数自然是2019减去前两个数。代码packagelanqiao;publicclassTestMain1
official 552 径。说明:叶子节点是指子节点节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所根节点到叶子节点路径为:1-2-5,1-3解题思路递归得方式遍历叉树(深度优先搜索),
数据结构与算法 5134 试题描述:思路:用数组表示完全叉树,用先序遍历方式遍历每一层节点,用一个数组储存每一层和,因为数据规模小于100000所以用一个容量为17数组即可。计完每一层和,再比较层数最小之和最大
weblog 4130 种在图形平面上,多个节点路径,求出最低通过成本。常用于游戏中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月  3 2022年09月  2 2022年10月  2
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。