Appearance
二分查找
二分查找算法也叫折半查找算法。
猜字游戏都应该玩过,随机写一个 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 个地方:
- 循环的退出条件
注意是 low <= high
,而不是 low < high
。
- mid 的取值
实际上,mid = (low + high) / 2
可能会溢出,因为如果 low 和 hight 都比较大的话,两者之和就可能溢出,改进方法是写成 low + (high - low) / 2
。或者更追求性能的话,可以写成位运算 low + ((high - low) >> 1)
。
- 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,那就无法使用二分查找了。