二分查找算法

二分查找算法

困而学,学而知

从今天开始写关于算法的文章,但是我不会专门的按照顺序来。因为平时工作的话,是没有这么多时间的。所以我是看到有什么地方用到某种算法,我就记录下来。

什么是二分查找算法?

首先需要说明的是,只要在数组有序的情况下,二分查找才是有用。如果是一个无序的数组,二分查找就没有意义了。

现在有1~100个数,当然是有序的,现在需要你猜一个数。你每猜一次,我告诉你猜大了还是猜小了,那么现在开始吧。

bisearch-origin

现在有三种方案

  1. 从1按照顺序猜

    我们来看看这种方式,如果从1按照顺序猜,最好的情况就是第1次就猜中,最坏的情况就是最后一次才会猜中。

  2. 第二种方案是乱猜,这种方案和第一种方案的的结果是一样,最好就是首次就猜中,最坏情况也是就是最后才猜中。

  3. 第三种方案则是使用我们今天要说二分查找法,那又如何使用二分查找法来猜呢?这种方案的最好和最坏的情况又分别的是什么,也就是和上面的两种方案比起来提升点到底在哪里呢?容我慢慢道来。

如何使用二分查找

  • 找到1100中间的数字,也就是50。我会告诉你大了还是小了,也可能运气好第一次就猜中了?

  • 我说大了,那你继续猜25,1和50中间的数字。我会告诉你小了。这时候我们就排除了比50打的数字,是不是对半分了,也就是所说的二分。

  • 继续猜38,26和50中间的数字,我说大了,这时候又会继续去找26到38之前的数字。

    ....

  • 以此类推,到最终找到我们想要的数字,最多会找几次呢?7

使用二分查找和上面两种方式的对比

显而易见的,如果使用二分查找,最好的情况都是一样的,以第1次就能查到。但是最坏的情况则不然,其他两种情况,最坏的情况需要100次,而使用二分查找只需要7次,效率显而易见。

专业人士就需要用专业解释。使用第一种方案查询是一种线性查询,查询的次数会根据需要查询的数量递增。也就是如果有n个数字,最多就需要查询n次。而使用二分查找最多只需要log2n次。(先不唠叨这个,后续会有单独的文章来唠叨)

从上面的对比来看,这个提升点肯定是在查询的次数上面了。那么还有其他的提升呢?

其实在算法的效率的对比上面一直有两个重要的点:空间时间。上面我们比较了空间复杂度,我们现在来看看他们的时间复杂度。

时间复杂度

这里直接说结论吧,第一种方案的时间复杂度是:O(n),二分查找法的时间复杂度是:O(logn)

这里不唠叨大O表示法,后面紧跟着唠叨。

想象一下,在亿的数量下,二分查找的效率有多高。

MySQL中B+树中节点内部数据查询就是用到了二分查找法

使用Java实现二分查找

说了这么多,还不如直接来一段代码

private static int binarySearch(long[] arr, int item) {
        int low = 0;
        // 最打的数字是数组长度-1
        int high = arr.length - 1;
        // 为什么是'<='? 因为如果直接使用arr.length可能会出现越界,
        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = arr[mid];

            if (midVal < item) {
                low = mid + 1;
            } else if (midVal > item) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
}

以上代码还存在的问题点

如果 low 和 high 的值比较大,low + high 相加可能造成溢出,我们可以使用 low + (high - low)

二分查找的局限性

二分查找的时间复杂度是 O(logn),查找数据的效率非常高。不过,并不是什么情况下都可以用二分查找,它的应用场景是有很大局限性的。那什么情况下适合用二分查找,什么情况下不适合呢?

二分查找只适用于数组

如果链表也想使用二分查找,其实是不可以的。主要是因为二分查找需要按照下标随机访问元素,而链表的访问指定下标元素的时间复杂度为O(n)。所以,如果数据使用链表存储,二分查找的时间复杂就会变得很高。

二分查找只适用于有序数组

我们可以看到,如果要找到中间值,就需要找到当前区间的最小值和最大值,这也就需要数组是有序的。如果数据没有序,我们需要先排序。排序的时间复杂度最低是 O(nlogn)。所以,如果我们针对的是一组静态的数据,没有频繁地插入、删除,我们可以进行一次排序,多次二分查找。这样排序的成本可被均摊,二分查找的边际成本就会比较低。

但是,如果我们的数据集合有频繁的插入和删除操作,要想用二分查找,要么每次插入、删除操作之后保证数据仍然有序,要么在每次二分查找之前都先进行排序。针对这种动态数据集合,无论哪种方法,维护有序的成本都是很高的。

二分查找只能用在插入、删除操作不频繁,一次排序多次查找的场景中。针对动态变化的数据集合,二分查找将不再适用。针对对动态数组集合,我们可以使用二叉树。

数据量太大和太小都不适用于二分查找

数据量太小使用二分查找太浪费空间,直接使用顺序遍历就可以了。

数据量太大的话,会占用连续的内存空间,得不偿失。比如说,要对 1GB 的有序数组进行二分查找,就需要占用连续的 1GB 的内存空间。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://baozi.fun/2019/09/06/binarysearch-algorithm

Buy me a cup of coffee ☕.