0%

算法之二分查找(上)

二分查找在平时的生活中也挺常用的,比如说以前玩的猜数游戏,每次都取中间数,然后得知是大了,还是小了,这个例子也就是二分查找。

比如下面的这个例子,要查找有没有数值19,其中low和high是查找的区间的下标,mid是查找区域的中间值的下标。

二分查找的思想是比较容易理解的,而且它的时间复杂度也是比较低的。假设数据大小为n,每次查找完后都会缩小一半,即为除以2,最坏的情况也就是一直到查找空间为空的时候,所以它们的变化为n,n/2,n/4,n/8,…,n/2k,当n/2k=1时,k即为缩小的次数,因为每次都只涉及到两个数的大小比较,所以k次操作的时间复杂度为O(k),又因为n/2k=1,所以k=log2n,时间复杂度也就是O(logn),这是一个非常恐怖的数量级了,比如n为2的32次方,大约是四十多亿,用二分查找来查找里面的一个数的话,最多比较32次也就可以得到这个值了,这是一个非常恐怖的情况。

上面的原理已经很明确了,所以二分查找的实现并不是很复杂,但是有一个前提条件,有序数组中不存在重复元素,只有在这个情况下,二分查找的实现才是相对简单的,具体的实现在下一篇文章里提及。


虽然二分查找时间复杂度低,查找起来非常高效,但它也有一定的适用条件的。

首先,二分查找是依赖于数组的,如果使用其他的数据结构来实现的话,二分查找的时间复杂度将会变的非常高,因为数组在下标随机访问的时候,时间复杂度是O(1),而链表随机访问的时间复杂度是O(n)。

而且它必须是有序的,前面也说过排序算法,时间复杂度最低的为O(nlogn),如果使用的场景是没有大量的插入和删除操作,一次排序可以多次查找的情况,那排序所的成本就可以被均摊,否则二分查找将不再适用,动态数据集合的查找,我们需要使用其他的算法才可以。

最后就是要注意要查找的数据量不能太大或者太小,太小的话,遍历就足以满足;太大的话,因为它是基于数组这种数据结构的,它所需要的连续的内存空间就是一个非常大的障碍。


参考文档

极客时间-数据结构与算法之美