前言故事:记得上小学的时候,有个体育老师跟我们玩了一个游戏,他说:"我背对着你们,然后班长在纸上写一个1000以内的数字,你们都看一下,不需要告诉我,然后我猜这个数字是多少,你们只需要告诉我,我猜的数字大了还是小了,那么我最多猜10次就能猜中,你们信不信?".

那么从上面的故事,我们可以分析出什么呢?

1.小编的数学是体育老师教的

2.老师10次内猜出了正确数字,小编知道了什么叫 "我伙呆!"

3.我们是时候学习二分查找算法了

二分查找算法

再来一个故事(同样原理) : 月底要开迎新晚会,这时候小白需要表演一个纸牌魔术,观众从红桃1~红桃13(红桃K)中随便抽取一张,小白打电话给小明,小明不在场,让小明说出观众抽取的牌是什么

这个魔术表演起来还是很炫酷的,那么我们现在就用程序来介绍这个魔术的原理.

魔术主程序

小明猜测与小白回答方法

原理介绍:

其实就是小明在电话那头每次猜测中间的那张牌,而小白只需要通过言语暗示小明猜测的牌应该更大些还是更小些(至于如何暗示可以与小明提前"串通"好),小明每次根据小白的提示缩小自己猜测的范围,由于2的4次方是16,即16以内的数字最多猜测4次即可.

提取公共方法:

上面举得魔术例子其实就是二分循环查找的方法,下面我们就把二分循环查找算法和二分递归查找算法敲一遍,大家就下面图中的内容理解一下:

二分循环查找法

二分递归查找法

总结:

下面我们总结下应用场景:

1. 升序数字集合

2. 利用二分递归查找或者二分循环查找

3. 二分查找的优点:比较次数少,查找速度快,平均性能好;

4. 二分查找的缺点:要求待查表为有序表,且插入删除困难;