美文网首页
数据结构与算法笔记day12:二分查找(上)

数据结构与算法笔记day12:二分查找(上)

作者: 楠楠喜欢泡枸杞 | 来源:发表于2019-05-14 22:51 被阅读0次

            二分查找(Binary Search)算法,也叫折半查找算法,是一种针对有序数据集合的查找算法。

        1无处不在的二分思想

            二分查找是一种非常简单易懂的快速查找算法,生活中到处可见,比如我们现在来做一个猜字游戏,随机写一个0-99之间的数字,来猜猜这个数字是多少。假设要猜的数字是23,那么二分查找的过程如下:

            我们可以看到,7次就猜出来了。按照这个思想,即便是0-999的数字,最多也只要10次就能猜中。

            再来一个例子,我们假设有10个订单,金额分别是:8,11,19,23,27,33,45,55,67,98。我们想要查询这个名单中是否有19这个金额的订单,还是利用二分思想,过程如下图,其中low和high表示待查找区间的下标,mid表示待查找区间的中间元素下标。

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

        2O(logn)惊人的查找速度

            二分查找非常高效,高效到什么程度呢?

            下面分析一下它的时间复杂度。

            最坏情况下,直到查找区间被缩小为空才停止,被查找区间的大小变化如下图:

            当n/2^k=1时,k的值就是总共缩小的次数。而每次缩小操作只涉及两个数据的大小比较,所以经过了k次区间缩小操作后时间复杂度就是O(k)。由n/2^k=1可得k=log2n,所以时间复杂度就是O(logn)。

            对数时间复杂度O(logn)是一种极其高效的时间复杂度,有时候甚至比时间复杂度是常量级O(1)的算法还要高效,为什么这么说呢?

            因为 logn 是一个非常“恐怖”的数量级,即便 n 非常非常大,对应的 logn 也很小。比如 n 等于 2 的 32次方,这个数很大,大约是 42 亿。也就是说,如果我们在42 亿个数据中用二分查找一个数据,最多需要比较 32 次。

            而我们之前有说过,用大O标记法表示时间复杂度的时候,会省略掉常数、系数和低阶,对于常量级时间复杂度的算法来说,O(1)可能表示的是一个非常大的常量值,比如O(1000)、O(10000)。因此常量级时间复杂度的算法有时候可能还没有O(logn)的算法执行效率高。

            反过来,对数对应的就是指数。指数时间复杂度的算法在大规模数据面前是无效的。

        3二分查找的递归与非递归实现

            最简单的情况就是有序数组中不存在重复元素,下面用Java代码实现一个最简单的二分查找算法。

            我的代码:

            运行结果:

            几个需要注意的点:

            1.循环退出条件是low<=high而不是low<high。

            2.mid取值一般写法为mid=(low+high)/2,但是如果low和high比较大的话,两者之和就有可能会溢出,改进的方法是将mid的计算方式写成low+(high-low)/2。更进一步,如果要将性能优化到极致的话,我们可以将这里的除以2操作转换成位运算low+((high-low)>>1)。因为相比除法运算来说,计算机处理位运算要快得多。

            注意这里哦,我第一次就犯了这个错呜呜:

            3.注意low和high的更新应该写为low=mid+1,high=mid-1,不能直接写成low=mid或者high=mid,否则可能会发生死循环。

            二分查找除了用循环来实现,也可以用递归来实现,代码如下:

            结果同上。

            戳这里查看源代码。

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

            首先,二分查找依赖的是顺序表结构,简单点说就是数组。

            二分查找不能依赖其他数据结构,比如链表。因为二分查找算法是按照下标随机访问元素,数组按照下标随机访问元素的时间复杂度是O(1),而链表随机访问的时间复杂度是O(n)。所以如果数据使用链表存储,二分查找的时间复杂度就会变得很高。

            因此,二分查找只能用在数据是通过顺序表来存储的数据结构上。

            其次,二分查找针对的是有序数据。

            二分查找的数据必须是有序的,如果没有序,需要先排序,而维持有序的时间成本比较高。

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

            如果数据量很小,完全没有必要二分查找,顺序遍历就OK了,因为两种方法时间都差不多,只有数据量大的时候,二分查找的优势才会比较明显。

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

            最后,数据量太大也不适合二分查找。

            二分查找的底层需要依赖数组这种数据结构,数组为了支持随机访问的特性,要求内存空间连续,对内存要求比较苛刻。所以太大的数据用数组存储就比较吃力,也就不能用二分查找了。

        5内容小结

            今天我们学习了一种针对有序数据的高效查找算法,二分查找,它的时间复杂度是O(logn)。二分查找的核心思想理解起来非常简单,有点类似分治思想,即每次都通过跟区间中的中间元素对比,将待查找的区间缩小为一般,直到找到要查找的元素,或者区间缩小为0。实现二分查找的代码需要注意三个容易出错的地方:循环退出条件、mid的取值、low和high的更新。

            二分查找虽然性能很棒棒,但是应用场景比较有限,比层必须依赖数组,并且还要求数据是有序的。对于较小规模的数据查找,我们直接使用顺序遍历就OK了,二分查找的优势并不明显。二分查找更适合处理静态数据,也就是没有频繁的数据插入、删除操作。

        6思考题

            1.如何编程实现“求一个数的平方根”?要求精确到小数点后6位。

            2.如果数据是用链表存储的,使用二分查找的时间复杂度是多少呢?

            后面有空了我再用代码实现查找平方根!

    相关文章

      网友评论

          本文标题:数据结构与算法笔记day12:二分查找(上)

          本文链接:https://www.haomeiwen.com/subject/ioyeaqtx.html