查看原文
其他

二分查找

涛声依旧 趣谈编程 2019-03-29

面试官:写个二分热热身

我心想:不用热身,热的手已经出汗了


二分查找有着查找速度快,平均性能好等优点,但必须要求待查表为有序表,且插入删除困难,面试比较常考,今天我们具体看一下二分


二分查找思想


前情回顾:克给谦子讲了冒泡排序[点击查看]


次日,克唤来两名得意弟子谦子和慧子,准备考考他们

谦子和慧子来到老师跟前,只见老师在纸上写了一行数,如下:

你们谁能用程序在最短的时间找出15?

只需要从第一个元素开始往后依次比较,比较六次就可以找到了

谦子

谦子抢先答道

我只需两次就可以找到

慧子

哦,如何做到的?

谦子

谦子急忙问道

老师给的数字是升序的,所以没有必要一个一个比较,可以逐渐缩小要查找的范围来查找,我先看中间的元素,如果是15,那就直接找到了,如果比15比中间的元素大,那就应该去中间元素的右边去找,反之在左边找

慧子

慧子一边说着一边画了个图


你看,我用名为arr的数组存储这些元素,用low和high两个变量去划定我查找的区间,第一次比较15大于中间元素8,那么下次我就在8的右边查找

慧子

这时慧子又画了一个图

这次查找区间变小了,同时也查找到了,一共就用了两次

慧子

谦子听了之后不得不佩服


慧子的思想非常好,这就是今天想给你说的二分查找

那如果查12呢?

谦子

如果查12,同样的思路,第一次查找和15一样,第二次查找12小于15,应该在15左边,8的右边查找

慧子

慧子画出了第三张图

这次只剩下10一个元素了,但是还是不相等,那就查找失败了,表明给定的元素中没有12这个元素

慧子


二分代码

请输入

那你能写出这个查找算法的代码吗?

没问题

慧子

慧子的代码功底还是非常强的,说着说着写了短短几行代码

你给我一个排好序的数组,和你要查的元素,我查到了给你返会该元素在数组中的位置,如果没有则返回-1

慧子

慧子解释道

这个low<=high的循环条件能不能改为low<high呢?

谦子

不行,如果改为 low < high,就有可能出现本来数组中有待查元素,却查不到的情况,比如查10,前两次查找和查12一样,最后low和high指向了元素10,但是此时while(low<high)不成立,所以会跳出循环

慧子

慧子画出了下图解释道

哦,我懂了,只有在low>high的时候循环才可以结束

谦子

你觉得你的程序写的怎么样,再检查检查

这时克发话了

慧子还在欣赏自认为完美无瑕的代码,听了老师的话一下变得紧张起来

这。。。看不出来

慧子

慧子嘿嘿地笑了一下

你看你的 mid = (low+high)/2 这行代码,low 和 high 都是整形,当你的low和high很大的时候,是不是 low+high 就会产生溢出,low+high 的结果就会变为负数,那么 (low+high)/2也就是负数了,程序运行时就错了


哦,原来是这样,那该如何解决呢?

慧子


给你两个容量相同杯子,里面水的体积不同,你该如何将两杯水变成体积相同呢?

你之前的做法就相当于把其中一个杯子的水倒入另一个杯子中,然后均分,这样有可能水会溢出,你现在换个思路,你先算出两个杯子水之前的差值,然后给水少的杯子倒入差值的一半,这不就两个杯子的水一样了吗?

克自问自答起来,顺手画了一个图


作者注:此例子为冒泡大神指点时所用例子

慧子恍然大悟,原来写成 mid=low+(high-low)/2 就可以了


时间复杂度

那你说说这个算法的时间复杂度

这个。。。,弟子不才,还请老师指点

慧子


要分析时间复杂度,其实也不难,只要算出while循环了几次就行了

你这样想一下,你要查找的数据规模如果是n,那二分一次后规模就变为n/2^1,二分两次后规模为n/2^2,...,二分m次后规模为n/2^m,若二分m次后跳出循环则m就是循环的次数(不管查找是否成功)

下来分析最坏情况,也就是查找不到

前提:查找不到元素

假设你二分m次后剩下一个元素,那么此时规模为1,同时二分m次后规模变为n/2^m,则:n/2^m = 1, 解出 m = lg(n),此时再循环一次,查找不到,跳出循环,所以说最多有 m+1 次循环(二分m次未跳出循环,还要二分一次),也就是查找一个元素最多需要m+1次,即lg(n)+1次比较,故二分的最坏时间复杂度为O(n) = lg(n)

lg(n) 这里是以2为底


说完克看弟子还是不是很明白,说道

就拿我们今天讨论的数分析吧,我们要查找25[为了使查找次数变的最大]

你看,查找25我们二分了两次后查找区间变为一个元素了,这时7/2^m=1;m=lg7=2(向下取整),再循环一次跳出循环,循环次数为3

哦,我懂了

慧子

x向下取整表示小于或等于x的最大整数

今天慧子表现不错



如果感觉不错,记得分享给好友哦

扫码关注,精彩不断

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存