Skip to content
On this page

二分查找

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

猜字游戏都应该玩过,随机写一个 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) 执行效率高。

实现二分查找

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

最简单的二分查找

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

js
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

  1. mid 的取值

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

  1. low 和 high 的更新

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

二分查找的局限性

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

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

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

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

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

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

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

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

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

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

二分查找 has loaded