《对分查找算法》PPT课件.ppt

《对分查找算法》PPT课件.ppt

ID:58114262

大小:325.83 KB

页数:10页

时间:2020-09-05

《对分查找算法》PPT课件.ppt_第1页
《对分查找算法》PPT课件.ppt_第2页
《对分查找算法》PPT课件.ppt_第3页
《对分查找算法》PPT课件.ppt_第4页
《对分查找算法》PPT课件.ppt_第5页
资源描述:

《《对分查找算法》PPT课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、对分查找算法有一个数在1~100之间,请大家用最少的次数来猜出这个数。你会先猜几?如果我告诉你这个数是15,按照刚才的逻辑,几次可以猜到这个数呢?在刚才的沟通中,其实隐藏着一个非常经典的算法—对分查找对分查找实施原理(1)对分查找是效率很高的查找方法,但被查找的数据必须是有序的。(2)首先将查找的数与有序数组内处于中间位置的数据比较,如果中间位置上的数与查找的数不同,根据有序性,就可确定应该在数组的前半部分还是后半部分继续查找。(3)在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。key=48时对分查找处理过程思考两个问题:①d(mid)

2、新查找的范围为下半部分,i和j的变化规律是怎样的?②如果要找的是52,最后i、j、mid分别是多少?key=17时对分查找处理过程思考:当d(mid)>key时,新查找的范围在哪里?i和j如何变化?总结:如果d(mid)>key,新查找范围为上半部分,i值不变,j=mid-1。key=20时对分查找处理过程总结:①找到了查找会结束。②在i<=j时重复查找,如果还是找不到,查找也会结束。对分查找的过程对各种情况进行归纳总结(1)key与d(mid)的大小比较影响i、j取值的规律:i的取值规律:如果d(mid)

3、d)>key,那么j=mid-1。(2)继续进行重复查找的条件:i≤j。对分查找的比较次数对于规模为n的数组进行对分查找,无论是否找到,最多进行+1次查找,表示小于等于的最大整数。相当于INT()对于有5000个元素的数组,使用对分查找,最多要查问多少个数据?使用顺序查找呢?试比较两种查找算法的效率。最多查找次数:对分+1=int()+1

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。