什么是二分查找?

期末考要来了,最近小秋正在从零开始复习算法相关知识….

一道简单的算法题

帅地:听说你最近正在临时饱佛教复习各种算法?

小秋:对啊,算法太难了,把我头都搞大了,不过,感觉自己复习的好像还不错。

帅地:那我找一道简单的题考考你?

小秋:好啊,好啊,正好可以试试水。

帅地:给你一个有序数组,例如

image-20231130014324163

然后我给出一个元素 target,你返回它对应数组的下标,如果数组中不存在这个元素的话,则返回 -1。例如

1、我给出 target = 18,则你需要返回 5。

2、我给出 target = 1,你需要返回 0。

3、我给出 target = 10,由于数组中不存在 10 这个元素,所以你需要返回 -1。

小秋:这也太简单了吧,我从左到右遍历数组所有元素,就可以找出来了。

image-20231130014337048

帅地:这是一种方法,不过你这种方法的时间复杂度为 O(n),有没有时间复杂度上更小的方法呢?

小秋:那我可以采用哈希表来存储,把数组元素作为 key,对应的下标作为 value,这样的话,以后需要查找某个元素了,我就可以在时间复杂度为 O(1) 找到对应的元素下标了。

帅地:你这种方法,需要用哈希表来存放元素,虽然时间复杂度为 O(1),但是空间复杂度为 O(n) 了,你能不能在时间复杂度和空间复杂度折中一下,找出更加优美的方法呢?

小秋:好像,,目前没啥思路。

神速的二分查找

帅地:你听说过二分查找吗?

小秋:二分查找?什么鬼?

帅地:这道题就可以用二分查找来解决了,我来给你讲讲吧。

小秋:好啊,好啊。

帅地:其实呢,对于这道题,由于数组是有序的,我们每次在查找的时候,可以直接从中间元素开始比较,例如我们要查找 target = 10,这个元素,我们把 target 与数组中间的那个元素 15,进行比较。

image-20231130014350634

(1)如果 target 比 15 小,那么 15 以及 15 右边的所有元素一定比 target 大,所以 target 只能存在于 15 的左边元素中。

(2)如果 target 比 15 大,那么 15 以及 15 左边的所有元素一定比 target 小,所以 target 只能存在于 15 的右边元素中。

(3)如果 target 与 15 相等,则直接把 15 对应的下标返回即可。

在这个例子中,target = 10 比 15 小,所以 target 只可能存在于 15 的左边元素中

image-20231130014405689

接下来我们只需要在左半部分查找这个元素就可以了,右半部分的元素可以不用管了,你看,通过这种方式,只需要一次比较,我们就可以把查找的范围缩小了一半。

接着我们继续把 target 与中间元素比较,这时候中间元素是 5,15比 5 大,所以 target 只可能存在于 5 右边的元素中

image-20231130014418745

接下来我们继续查找,这时中间元素是 10,和 target 相等,所以直接把 10 的下标 index = 2 返回。

二分查找的本质

帅地:小秋啊,这种每次都从中间元素开始比较,并且一次比较后就能把查找范围缩小一半的方法,就叫做二分查找了,这种二分查找的时间复杂度是 O(logn),空间复杂度是 O(1),可以说非常快的了。

小秋:那什么情况下可以使用二分查找这种方法呢?

帅地:要使用二分查找,给的数据需要具备两个基本的特性

(1)给的数据是有序的。

(2)给的数据支持随机访问

小秋:什么是随机访问呢?

帅地:例如像数组就支持随机访问了,例如你要访问第 5 个元素,那么你就可以用下标为 4,即 arr[4] 来快速访问第五个元素了。而链表就不支持随机访问了,例如你要访问链表的第 5 个元素,你无法像数组那样,直接用下标来定位,只能从链表头部一个一个遍历到第五个。

小秋:哦,我知道了,只有支持随机访问,我们才能根据数组最左边和最右边的下标,直接定位到数组的中间元素。

帅地:是的,那你可以根据刚才那道题写一下代码吗?

小秋:没问题。

    public static int binarySearch(int target, int[] arr) {
        // 数组最左边元素下标
        int left = 0;
        // 数组最右边元素下标
        int right = arr.length - 1;
        while (left <= right) {
            // 中间元素下标
            int mid = (right + left) / 2;
            if (arr[mid] > target) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                return arr[mid];
            }
        }
        return -1;
    }

90% 的人都会犯的错误

帅地:你写的基本正确,不过有个小问题,就是算中间元素下标那里

mid = (left + right) / 2;

你这种方法有时候会产生溢出的哦。例如,我们知道 int 整数的最大值大概是 2^31 – 1 大概为 21 亿。而 left 和 right 这两个数相加是有可能超过 21 亿的,例如 left = 12亿,right = 13 亿。这个时候,两个数的和超过了最大值,就会产生溢出了。

小秋:那该怎么写?

帅地:正确的写法应该是这样的

mid = left + (right - left) / 2;

这样,就能保存不会出现溢出的情况了。

二分查找在生活中的骗局

帅地:其实在我们的生活中,二分查找也是有挺多应用的,例如用二分查找来做坏事。

小秋:坏事?可以给我举例看看吗?

帅地:有时候临近一些比赛了,例如全世界性的足球大赛,有时候我们会收到一些邮件,有人谎称他会神预算,例如今天是德国和法国比赛,他会跟你说一定是德国胜,然后跟另外一部分人今天一定是法国胜。

而德国和法国,总有一个人会胜,那么他可以跟 10000人说德国胜,10000人说法国胜。我们假如是德国胜了,那么在 10000 人看来它的预算是正确的。

接着德国和俄罗斯比赛,它会在那 10000 人中,跟 5000人说德国胜,5000人说俄罗斯胜。那么在 5000 看来它的预算还是正确的….

就这样,每次它都从被他预算正确的那一部分人继续吹他会神预算,那么在有些人看来,他果真连续预算正确,这个时候,这些人可能就会认为,他真的有神预算的能力,于是,可能就会相信它说的话了,进而就会被他所欺骗。

小秋:虽然我没收到这类邮件,但是我经常收到一些六合彩的短信

image-20231130014438050

帅地:是的,这些,就是利用的二分查找的思想了。

二分查找?没有你想的那么简单

帅地:小秋啊,刚才给你讲的那道题,可以说是最简单的了,其实,对于二分查找,有很多变形题的,往往不会那么简单。

小秋:那你可以给我出几道,看我能不能现学现卖。

帅地:那我给你两道题吧。

1、实现 pow(x, n)函数:即计算 x 的 n 次方。

2、搜索选择排序数组:假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

这两道题,可以说是中等难度的变形题了,跟我说说怎么做?

小秋:这….,我才刚学完,能不能给我点时间让让想想?

帅地:大概多长呢?

小秋:不长,两天时间就可以了。

帅地:两天 还不长…… 好吧,那两天后见。

总结

这次主要讲解了二分查找的基本思想以及生活在的例子,二分查找思想虽然不难,不过却有很多不容易的题。

发表回复

后才能评论