对分查找授课课件

课件16张PPT。对分查找湄池中学 吴招丹猜价格游戏规则：
1.不能抢答，
举手回答。
2.若猜对就
把MP3送
给你。
猜价格5075888184中间值m：m=int( (i+j)/2 )
m=fix ( (i+j)/2 )m= (i+j)2 或对分查找的前提条件例1:数组有7个元素，依次15、1、2、18、5、10、4，若采用对分查找法在该数组中查找数据10，需要查找的次数是(　　)
A.1 B.2 C.3 D.4注意：对分查找的数据必须有序C1、2、4、5、10、15、18将查找的数key与有序数组内的中间位置d(m) 的数据比较
若key与d(m)相同，则找到;
若key与d(m)不同，根据数据的有序性，就可确定key在该数组的前半部分还是后半部分;
在确定的新范围内，继续按上述方法进行查找，直到获得最终结果（或找不到结果）。
对分查找的基本思想对分查找的流程图（升序）i←m+1j←m-1对分查找的代码（升序）p=0：i=1：j=n
do while i<=j
m= (i+j)2
if key=d(m) then
p =m
exit do
elseif key>d(m) then
i=m+1
else
j=m-1
end if
loop小王去药店买人参，发现店老板称量时的过程是这样子的 ：先放置100克砝码，砝码偏重；再将砝码改为50克，砝码偏轻；又将砝码改为70克，……通过这种策略，老板很快完成称重工作。此过程借鉴的算法是(　　)

A．顺序查找 B．排序
C．对分查找 D．累加
例2C例3：我校电子图书馆网站有1000本关于信息技术方面的图书（已索引排序），假设从中取出一条记录并与待查找项比较所花费的时间是10毫秒，则用对分法在该系统中查找任意一本图书最多花费的时间约为（ ）
A．100毫秒 B．50毫秒
C．170毫秒 D．110毫秒 查找次数的估算最少：1次
最多：Int(log2n )+1次A一个包含10万个人名的电话簿中找一个电话号码，用对分查找最多17次就可以找到。
将全国13亿人按身份证号排列后，你可以最多进行31次比较后找到这个人的信息。对分查找的实际意义效率高 元旦晚会马上举行了，评委老师正在筛选节目，现评委要查看各节目的资料，表格里是高二年级的9个节目，用对分查找法快速找到6号节目前已经访问了哪几号节目( )
A. 4 6
B．5 8 6
C．5 7 6
D．4 8 6例4 C在筛选时，8个评委老师对6号节目进行打分，成绩分别为
采用对分查找算法查找成绩12.8需要几次（ ）
A. 4 B. 3 C. 2 D. 1例5B总结
哪个查找算法能较快找到Alice，
查找次数是多少？
② 哪个查找算法能较快找到 Grace，
查找次数是多少？例6顺序查找 1次对分查找 3次总 结总结:顺序查找与对分查找比较i=m+1j=m -1m= (i+j)2 或 m=int((i+j)/2)1次n次1次Int(log2n )+1次数据需有序无低高1.认真理解练习本p116-118上的内容
2.完成p118-120的习题作业算法的三种基本结构选择结构顺序结构循环结构Do While 条件
语句块
LoopFor　i　=　初值 To 终值 [ Step 步长 ]
语句块
Next i If 条件 Then
语句块1
Else
语句块2
End If