文章目录
- 无处不在的二分思想
- 二分查找惊人的查找速度
- 二分查找的递归与非递归实现
- 1.循环退出条件
- 2.mid的取值
- 3.low和high的更新
- 最后说一句
![](/Files/SrcImg/?url=https://img-blog.csdnimg.cn/f9629fb28d534ac788b27d15bccee1d7.png)
🐱🐉作者简介:大家好,我是黑洞晓威,一名大二学生,希望和大家一起进步。
👿本文收录于 算法,本专栏是针对大学生、初学算法的人准备,解析常见的数据结构与算法,同时备战蓝桥杯。
无处不在的二分思想
二分查找是一种非常简单易懂的快速查找算法,生活中到处可见。比如说,我们现在来做一个猜字游戏。我随机写一个0到99之间的数字,然后你来猜我写的是什么。猜的过程中,你每猜一次,我就会告诉你猜的大了还是小了,直到猜中为止。你来想想,如何快速猜中我写的数字呢?
假设我写的数字是23,你可以按照下面的步骤来试一试。(如果猜测范围的数字有偶数个,中间数有两个,就选择较小的那个。)
7次就猜出来了,是不是很快?这个例子用的就是二分思想,按照这个思想,即便我让你猜的是0到999的数字,最多也只要10次就能猜中。不信的话,你可以试一试。
看懂这两个例子,你现在对二分的思想应该掌握得妥妥的了。我这里稍微总结升华一下, 二分查找针对的是一个有序的数据集合,查找思想有点类似分治思想。每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0。
二分查找惊人的查找速度
二分查找是一种非常高效的查找算法,高效到什么程度呢?我们来分析一下它的时间复杂度。
我们假设数据大小是n,每次查找后数据都会缩小为原来的一半,也就是会除以2。最坏情况下,直到查找区间被缩小为空,才停止。
可以看出来,这是一个等比数列。其中n/2k=1时,k的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较,所以,经过了k次区间缩小操作,时间复杂度就是O(k)。通过n/2k=1,我们可以求得k=log2n,所以时间复杂度就是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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
这个代码我稍微解释一下,low、high、mid都是指数组下标,其中low和high表示当前查找的区间范围,初始low=0, high=n-1。mid表示[low, high]的中间位置。我们通过对比a[mid]与value的大小,来更新接下来要查找的区间范围,直到找到或者区间缩小为0,就退出。如果你有一些编程基础,看懂这些应该不成问题。现在,我就着重强调一下 容易出错的3个地方。
1.循环退出条件
注意是low<=high,而不是low<high。
2.mid的取值
实际上,mid=(low+high)/2这种写法是有问题的。因为如果low和high比较大的话,两者之和就有可能会溢出。改进的方法是将mid的计算方式写成low+(high-low)/2。更进一步,如果要将性能优化到极致的话,我们可以将这里的除以2操作转化成位运算low+((high-low)>>1)。因为相比除法运算来说,计算机处理位运算要快得多。
3.low和high的更新
low=mid+1,high=mid-1。注意这里的+1和-1,如果直接写成low=mid或者high=mid,就可能会发生死循环。比如,当high=3,low=3时,如果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, mid+1, high, value);
} else {
return bsearchInternally(a, low, mid-1, value);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
最后说一句
感谢大家的阅读,文章通过网络资源与自己的学习过程整理出来,希望能帮助到大家。
才疏学浅,难免会有纰漏,如果你发现了错误的地方,可以提出来,我会对其加以修改。