二分查找 #

二分查找算法也叫折半查找算法。

猜字游戏都应该玩过，随机写一个 0 到 99 之间的数字，然后猜一下是什么？猜的过程中，每猜一次会告诉你大了还是小了，知道猜中为止。如何快速猜中写的数字？

通过二分查找，最多 7 次就可以猜中。

二分查找的核心思想 #

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

极快的查找速度 #

二分查找每次将数据范围缩小为原来的一半，现在假设数据量大小为 n，最坏情况下，知道查找区间被缩小为空，才停止：

// 查找区间的变化
n，n/2，n/4，...，n/2^k，...

当 n/2^k = 1 时，就是最后一次查找，此时 k 的值就是查找的次数。时间复杂度为 O(k)，而 k = log2n，所以时间复杂度就是 O(logn)。这是一个对数时间复杂度，它极其高效。

比如，n 等于 2^32，如果在这么多的数据中用二分查找一个数据，最多需要比较 32 次。

用大 O 表示法的时候，省略了常数、系数和低阶。所以对于一个常量级的算法来说，O(1) 可能是一个非常大的常量值，比如 O(100)、O(1000)，这个时候，它们可能还没有 O(logn) 执行效率高。

实现二分查找 #

二分查找其实也有好几种，先写一个简单的二分查找。

最简单的二分查找 #

最简单的情况就是有序数组中不存在重复的元素，用二分查找值等于给定值的元素。

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

容易出错的 3 个地方：

1. 循环的退出条件

注意是 low <= high，而不是 low < high。

2. mid 的取值

实际上，mid = (low + high) / 2 可能会溢出，因为如果 low 和 hight 都比较大的话，两者之和就可能溢出，改进方法是写成 low + (high - low) / 2。或者更追求性能的话，可以写成位运算 low + ((high - low) >> 1)。

3. low 和 high 的更新

low = mid + 1，high = mid - 1。这一这里需要 +1 和 -1，而不能直接写成 low = mid 和 high = mid，否则可能会造成死循环。比如 high = 3，low = 3，如果 arr[3] 不等于 target 就会死循环了。

二分查找的局限性 #

虽然二分查找效率很高，但是应用场景有很多的局限性。

1. 依赖数组这种顺序表结构

二分查找需要按照下标随机访问元素，数组按照下标随机访问数据的时间复杂度是 O(1)。它不能依赖于其它数据结构，比如链表，链表的随机访问时间复杂度是 O(n)，如果使用链表来存储，二分查找的复杂度会高很多。

2. 二分查找针对的是有序数据

二分查找对这一点比较苛刻，数据必须是有序的。如果数据没有序，需要先排序。如果针对的是一组静态的数据，没有频繁的插入和删除，那就可以进行一次排序，然后多次查找。而对于频繁插入和删除的，需要每次插入、删除的时候保证数据仍然有序，或者每次二分查找之前都进行排序。这种动态的数据，无论什么方法，效率都不高了。

所以二分查找还只能用在不频繁插入、删除，可以一次排序多次查找的场景。而频繁插入、删除就应该使用二叉树了。

3. 数据量太小不适合二分查找

数据量太小完全没有必要，直接遍历就好。不管有个例外，如果数据之间的比较很耗时，这个时候，不管数据量大小都推荐二分查找，可以减少比较次数。例如，从数组中找出值等于给定值的时候，每一个元素都是长度超过 300 的字符串，如此长的字符串之间比较很耗时，推荐二分查找，减少比较次数。

4. 数据量太大也不适合二分查找

因为二分查找依赖数组，而数组需要的是连续的内存空间。如果有 1 GB 的数据，那也就意味着需要 1GB 的连续空间，如果此时剩余 2 GB 空间，但是没有连续的 1 GB，那就无法使用二分查找了。