算法-没有bug的二分查找

硅谷探秘者 4755 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;
		}
	}


猜你喜欢
数据结构与算法 2642 题目:在一个序数组中指定数,如果存在返回其数组下标,否则返回-1packagetest;/*** *@author硅谷探秘者(jia)*/publicclassTestMain2
其他 58 1.vim命令2.使用apt-get命令安装命令如下:apt-getinstallvim3.执行过程可能会报错如下:1.如果进入容器时指定root用户,则可能会报错
weblog 8687 什么是floyd在计机科学中,Floyd-Warshall是一种在具正或负边缘权重(但负周期)加权图中到最短路径单个执行将到所顶点对之间最短路径长度(加权
数据结构与算法 11223 (returnnewint[]={1,2}),如果返回-1(returnnewint[]={-1,-1})。:用表解决问题实现:packageclub.test;importjava.util.HashMap;im
数据结构与算法 5458 题目描述思路:枚举,只需要枚举前两个数,满足条件第三个数自然是2019减去前两个数。代码packagelanqiao;publicclassTestMain1
数据结构与算法 4386 试题描述:思路:用数组表示完全叉树,用先序遍历方式遍历每一层节点,用一个数组储存每一层和,因为数据规模小于100000所以用一个容量为17数组即可。计完每一层和,再比较层数最小之和最大
weblog 2620 种在图形平面上,多个节点路径,求出最低通过成本。常用于游戏中NPC移动计,或线上游戏BOT移动计上。该像Dijkstra一样,可以到一条最短路径;也像BFS一样,进行启发
工具 2626 publicstaticvoidmain(String[]args){ inta=3;intb=9;NumberFormatnumberFormat=NumberFormat.getInstance();numberFormat.setMaximumFractionDigits(2);Stringresult=numberFormat.format((float)a/(float)b*100);S
归档
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月  4
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git undefined undefined sdf sdf dsdf sdfasdfasd sdf ppp sdf fggdgsd kkk kkk kkk sdddf 456
目录