二分查找及其应用课件.ppt
《二分查找及其应用课件.ppt》由会员分享,可在线阅读,更多相关《二分查找及其应用课件.ppt(21页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、二分查找及其应用 By ElemenT今天,你今天,你ACAC了吗?了吗?NO!NO!YES!YES!请在这里输入您的标题刷题太无聊?我们玩游戏吧!相信大家都玩过猜数字的相信大家都玩过猜数字的游戏。两人游戏,游戏。两人游戏,A同学在心同学在心里默念一个整数里默念一个整数n(1=n=1000)。)。B同学猜同学猜n是多少。是多少。同时如果同时如果B没有猜对,没有猜对,A告诉告诉他这个数比默念的数高了还他这个数比默念的数高了还是低了。是低了。最坏情况下,最坏情况下,ElemenTElemenT也也不不用用超超过过十次可以猜出!十次可以猜出!最坏情况下需要多少次呢?看起来好厉害的样子其实并不是,下面
2、将引入其实并不是,下面将引入“二二分搜索分搜索”的概念。的概念。如上述的游戏中,第一次应该如上述的游戏中,第一次应该取多少呢?取多少呢?500!很不巧并不是很不巧并不是500,而是一个比,而是一个比500大的数。大的数。虽然运气不好,但是虽然运气不好,但是B将区间的将区间的范围砍掉了一半!范围砍掉了一半!那么下一次那么下一次B该猜什么。该猜什么。大家已经发现,问题变成了501-501-10001000之间猜一个数,那么应该猜(501+1000)/2=750!(501+1000)/2=750!如果运气还是不好,又猜小了.没关系!只猜了仅仅两次,我们就将区间缩小为 751-1000.751-100
3、0.那么继续下去.我们发现,每次可以将区间缩小为原来的一半。递减速度显然就是loglog级别的。log(1000)log(1000)向上取整只有10.10.那么我们一定可以在1010次之内猜出这个数。给定一个有序序列a0,a1,a2.aN,给出一个目标值tg,在序列中查找是否存在tg,如果存在,返回tg的下标。如何快速查找?我们必须看到数列是有序的充分利用有序的条件,类似猜充分利用有序的条件,类似猜数一样查找数一样查找tg。复杂度为复杂度为log(n)。那么我们来看看如何实现二分那么我们来看看如何实现二分查找。查找。int bs(int*a,int n,int tg)int l=0,r=n-1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二分 查找 及其 应用 课件
限制150内