“二分”带来“十分”快感——二分思想的奥秘解析

🐱‍🐉作者简介：大家好，我是黑洞晓威，一名大二学生，希望和大家一起进步。
👿本文收录于 算法，本专栏是针对大学生、初学算法的人准备，解析常见的数据结构与算法，同时备战蓝桥杯。

无处不在的二分思想

二分查找是一种非常简单易懂的快速查找算法，生活中到处可见。比如说，我们现在来做一个猜字游戏。我随机写一个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;
}

这个代码我稍微解释一下，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);}
}

最后说一句

感谢大家的阅读，文章通过网络资源与自己的学习过程整理出来，希望能帮助到大家。

才疏学浅，难免会有纰漏，如果你发现了错误的地方，可以提出来，我会对其加以修改。