驻马店制作网站的公司,国内服务器免备案方法,网站设计规划报告,电子商务有限公司简介文章目录无处不在的二分思想二分查找惊人的查找速度二分查找的递归与非递归实现1.循环退出条件2.mid的取值3.low和high的更新最后说一句#x1f431;#x1f409;作者简介#xff1a;大家好#xff0c;我是黑洞晓威#xff0c;一名大二学生#xff0c;希望和大家一起进…
文章目录无处不在的二分思想二分查找惊人的查找速度二分查找的递归与非递归实现1.循环退出条件2.mid的取值3.low和high的更新最后说一句作者简介大家好我是黑洞晓威一名大二学生希望和大家一起进步。 本文收录于 算法本专栏是针对大学生、初学算法的人准备解析常见的数据结构与算法同时备战蓝桥杯。 无处不在的二分思想
二分查找是一种非常简单易懂的快速查找算法生活中到处可见。比如说我们现在来做一个猜字游戏。我随机写一个0到99之间的数字然后你来猜我写的是什么。猜的过程中你每猜一次我就会告诉你猜的大了还是小了直到猜中为止。你来想想如何快速猜中我写的数字呢
假设我写的数字是23你可以按照下面的步骤来试一试。如果猜测范围的数字有偶数个中间数有两个就选择较小的那个。 7次就猜出来了是不是很快这个例子用的就是二分思想按照这个思想即便我让你猜的是0到999的数字最多也只要10次就能猜中。不信的话你可以试一试。 看懂这两个例子你现在对二分的思想应该掌握得妥妥的了。我这里稍微总结升华一下 二分查找针对的是一个有序的数据集合查找思想有点类似分治思想。每次都通过跟区间的中间元素对比将待查找的区间缩小为之前的一半直到找到要查找的元素或者区间被缩小为0。
二分查找惊人的查找速度
二分查找是一种非常高效的查找算法高效到什么程度呢我们来分析一下它的时间复杂度。
我们假设数据大小是n每次查找后数据都会缩小为原来的一半也就是会除以2。最坏情况下直到查找区间被缩小为空才停止。 可以看出来这是一个等比数列。其中n/2k1时k的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较所以经过了k次区间缩小操作时间复杂度就是O(k)。通过n/2k1我们可以求得klog2n所以时间复杂度就是O(logn)。
因为logn是一个非常“恐怖”的数量级即便n非常非常大对应的logn也很小。比如n等于2的32次方这个数很大了吧大约是42亿。也就是说如果我们在42亿个数据中用二分查找一个数据最多需要比较32次。
二分查找的递归与非递归实现
实际上简单的二分查找并不难写注意我这里的“简单”二字。讲到二分查找的变体问题那才是真正烧脑的。今天我们来看如何来写最简单的二分查找。
最简单的情况 就是 有序数组中不存在重复元素我们在其中用二分查找值等于给定值的数据。我用Java代码实现了一个最简单的二分查找算法。
public int bsearch(int[] a, int n, int value) {int low 0;int high n - 1;while (low high) {int mid (low high) / 2;if (a[mid] value) {return mid;} else if (a[mid] value) {low mid 1;} else {high mid - 1;}}return -1;
}
这个代码我稍微解释一下low、high、mid都是指数组下标其中low和high表示当前查找的区间范围初始low0 highn-1。mid表示[low, high]的中间位置。我们通过对比a[mid]与value的大小来更新接下来要查找的区间范围直到找到或者区间缩小为0就退出。如果你有一些编程基础看懂这些应该不成问题。现在我就着重强调一下 容易出错的3个地方。
1.循环退出条件
注意是lowhigh而不是lowhigh。
2.mid的取值
实际上mid(lowhigh)/2这种写法是有问题的。因为如果low和high比较大的话两者之和就有可能会溢出。改进的方法是将mid的计算方式写成low(high-low)/2。更进一步如果要将性能优化到极致的话我们可以将这里的除以2操作转化成位运算low((high-low)1)。因为相比除法运算来说计算机处理位运算要快得多。
3.low和high的更新
lowmid1highmid-1。注意这里的1和-1如果直接写成lowmid或者highmid就可能会发生死循环。比如当high3low3时如果a[3]不等于value就会导致一直循环不退出。
如果你留意我刚讲的这三点我想一个简单的二分查找你已经可以实现了。 实际上二分查找除了用循环来实现还可以用递归来实现过程也非常简单。
我用Java语言实现了一下这个过程正好你可以借此机会回顾一下写递归代码的技巧。
// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {return bsearchInternally(a, 0, n - 1, val);
}private int bsearchInternally(int[] a, int low, int high, int value) {if (low high) return -1;int mid low ((high - low) 1);if (a[mid] value) {return mid;} else if (a[mid] value) {return bsearchInternally(a, mid1, high, value);} else {return bsearchInternally(a, low, mid-1, value);}
}
最后说一句
感谢大家的阅读文章通过网络资源与自己的学习过程整理出来希望能帮助到大家。
才疏学浅难免会有纰漏如果你发现了错误的地方可以提出来我会对其加以修改。
