二分查找

面试官：写个二分热热身 我心想：不用热身，热的手已经出汗了

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

二分查找思想

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

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

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

你们谁能用程序在最短的时间找出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的最大整数

”

克

今天慧子表现不错

完