15-二分查找（上）：如何用最省内存的方式实现快速查找功能？

Posted on | Post modified:
Words count in article: 2k | Reading time ≈ 7

开篇问题

假设这里有1000万个整数数据，每个数据占8个字节，如何设计数据结构和算法，快速判断某个整数是否在这1000万数据中？我们希望这个功能不要占用太多的内存空间，最多不要超过100MB，你会怎么做？

二分查找

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。

我们可以很容易的发现，二分的每次折半操作会使待查找的空间呈指数下降，这样：

binarySearch

当n/(2^k) = 1 时，k的值为总共缩小的次数，经过k次区间缩小操作，时间复杂度就是O(k)。由于k = log2(n)，所以时间复杂为O(logn)。

二分查找的非递归实现

下面是一个简单二分查找的非递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 二分查找: 查找某个给定值，并且假设没有重复
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. 循环退出条件
    注意是 low <= high，而不是 low < high。
  2. mid的取值
    我们需要注意，当low和high的值比较大时，mid的取值可能会发生溢出。这里我们可以将代码改进一下，写成low + (high - low)/2。或者这样写：low + ((high - low) >> 1)（注意，不能写成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，就会导致一直循环不退出。

二分查找应用场景的局限性

虽然二分查找的时间复杂度是O(logn)，查找的效率非常高。不过，并不是什么情况下都可以用二分查找，它的应用场景是有很大的局限性的。

首先，二分查找依赖的是顺序表结构——数组

因为二分查找需要根据数组下标随机访问元素。我们知道，数组按照下标随机访问数据的时间复杂度是O(1)，而链表随机访问的时间复杂度为O(n)。所以，如果数据使用链表存储，二分查找的时间复杂度会变得很高。

其次，二分查找针对的是有序序列

我们根据二分查找的思想，这个很容易理解。但是，如果我们的数据集合有频繁的插入和删除操作，要想用二分查找，我们就需要在进行查找之前先进行排序，这样的维护成本将会变得很高。所以，对于二分查找，最好的应该是，可一次排序多次查找这样静态的数据。

再次，数据量太小不适合二分查找

如果数据量很小，我们直接顺序遍历就好了。只有当数据量比较大的时候，二分查找的优势才会比较明显。

不过，有一个例外。如果数据之间的比较操作非常耗时——比如数组中存储的都是长度超过300的字符串，不管数据量大小，都推荐用二分查找。

最后，数据量太大也不合适

第一点讲到，二分是用数组来实现的，而数组要求连续的内存空间。如果数据量过大，比如1GB，那我们即便有2GB的剩余空间，而这剩余的空间都是零散的，也仍然无法申请到足够的内存空间。

解答开篇

问题是说，我们需要在内存不超过100MB的情况下，在1000万个整数中快速查找某个整数。

看完了二分的理论就很容易可以解决这个问题啦！每个数据大小是8个字节，如果将数据存进数组中，预计内存是80MB左右，满足要求。先使用快排进行排序，接着再将查找数据。1000万在2^23和2^24之间，因此最多需要比较24次就能找到！

注，老师在文章中提到，使用散列表、二叉树也支持快速查找动态数据(因为这两数据结构需要额外的内存空间，所以在内存上不满足需求)，由于我(笔者)还不熟悉这两种结构(准确来说emmm，之前学的以后毫无保留的还给我老师了。。)就暂时不写出来了。等之后复习到这两种结构时再返回来看看这个问题，顺便再复习一下。先在这里立个flag。

内容小结

这一篇讲了一种有序数据的高效查找算法——二分查找，它的时间复杂度时O(logn)。

二分查找的核心思想非常简单，有点类似分治思想。即每次比较都会将区间折半，直到找到需要查找的元素或者区间被缩小为0.但是二分查找的代码实现比较容易写错。需要重点掌握三个容易出错的地方：循环退出条件、mid的取值、low和high的更新。

二分查找虽然性能比较优秀，但是应用场景还是比较有限。底层依赖数组，还要求数据有序。对于规模比较小的数据直接顺序遍历就行，二分查找更适合处理没有频繁数据插入、删除操作的静态数据。

课后思考

  1. 如何编程实现 “求一个数的平方根” ？要求精确到小数点后6位。
  2. 如果数据使用链表存储，二分查找的时间复杂度会变得很高，那查找的时间复杂度究竟是多少呢？

@蒋礼锐

因为要精确到后六位，可以先用二分查找出整数位，然后再二分查找小数第一位，第二位，到第六位。

整数查找很简单，判断当前数小于+1后大于即可找到，

小数查找举查找小数后第一位来说，从x.0到(x+1).0，查找终止条件与整数一样，当前数小于，加0.1大于，

后面的位数以此类推，可以用x*10^(-i)通项来循环或者递归，终止条件是i>6，

想了一下复杂度，每次二分是logn，包括整数位会查找7次，所以时间复杂度为7logn。空间复杂度没有开辟新的储存空间，空间复杂度为1。

@Jerry银银

说说第二题吧，感觉争议比较大:
假设链表长度为n，二分查找每次都要找到中间点(计算中忽略奇偶数差异):
第一次查找中间点，需要移动指针n/2次；
第二次，需要移动指针n/4次；
第三次需要移动指针n/8次；
……
以此类推，一直到1次为值

总共指针移动次数(查找次数) = n/2 + n/4 + n/8 + …+ 1，这显然是个等比数列，根据等比数列求和公式：Sum = n - 1.

最后算法时间复杂度是：O(n-1)，忽略常数，记为O(n)，时间复杂度和顺序查找时间复杂度相同

但是稍微思考下，在二分查找的时候，由于要进行多余的运算，严格来说，会比顺序查找时间慢

有问题？发送 issues 给我~

0%