算法-没有bug的二分查找

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



评论区
请写下您的评论...
暂无评论...
猜你喜欢
数据结构与算法 3980 题目:在一个序数组中指定数,如果存在返回其数组下标,否则返回-1packagetest;/*** *@author硅谷探秘者(jia)*/publicclassTestMain2
数据结构,算法基础 766 理一些不交集(DisjointSets)合并及询问题。一个联合-(union-findalgorithm)定义了两个用于此数据结构操作: Find:确定元素属于哪一个子集。它可以被用
其他 5806 1.vim命令2.使用apt-get命令安装命令如下:apt-getinstallvim3.执行过程可能会报错如下:1.如果进入容器时指定root用户,则可能会报错
weblog 10372 什么是floyd在计机科学中,Floyd-Warshall是一种在具正或负边缘权重(但负周期)加权图中到最短路径单个执行将到所顶点对之间最短路径长度(加权
数据结构与算法 12595 (returnnewint[]={1,2}),如果返回-1(returnnewint[]={-1,-1})。:用表解决问题实现:packageclub.test;importjava.util.HashMap;im
official 1190 径。说明:叶子节点是指子节点节点。示例:输入:1/\23\5输出:["1-2-5","1-3"]解释:所根节点到叶子节点路径为:1-2-5,1-3解题思路递归得方式遍历叉树(深度优先搜索),
数据结构与算法 6857 题目描述思路:枚举,只需要枚举前两个数,满足条件第三个数自然是2019减去前两个数。代码packagelanqiao;publicclassTestMain1
数据结构与算法 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 加密算法
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。