2.4 查找 课件（18张幻灯片）

课件18张PPT。查找算法活动一:问题探究 问题1:如何在别人的一大串没写标签的钥匙中找出一把锁的钥匙？ 问题2:猜猜老师手中这本书的价格是多少？（价格为正整数，价格在40以内） 任务单1.已知数组d中存放了33.62.17.54.29.75.48,现在要查找75,将如何查找? 任务单2.已知数组a中存放了13.27.31.49.55.68,现在要查找27,将如何查找? 数组d中存放的数据是无序的数据,只能从第一个开始向后依次向后查找,或从最后一个开始依次向前查找. 数组a中存放的数据是有序的数据,能从第一个开始向后依次向后查找,或从最后一个开始依次向前查找,还可以怎样查找呢?活动二:任务单及分析算法思想:顺序查找的基本思想:从第一个数据开始,按数列的顺序逐个将数据与给定的值进行比较,若某个数据和给定值相等,则查找成功,找到所查数据的位置;反之,查找不成功. (1)利用循环语句(通常是for)逐个扫描; (2)在循环体内部利用选择语句(if)进行比对; (3)若查找成功,可以直接结束循环(Exit For).顺序查找算法的实现要点:顺序查找算法的流程图:输入要查找的数据K eyDim i, key as integer 输入要查找的数据Key For i=1 to n if d(i)=key then 找到,输出i exit for endif Next i If i>n then 未找到,输出0 顺序查找算法程序的基本框架:算法思想:对分查找的基本思想:又名二分查找,是一种高效的查找方法,前提是被查找的数据必须是有序的.先将处于中间位置的数据与查找键进行比较,若相等则查找成功;否则根据数组的有序性判断要查找键在前半部分还是后半部分,然后缩小范围按以上方法继续查找,直至找到要查找的数据,或直到数据不存在. 用对分查找在下列数组中查找２７任务单： １．在这个查找中，i的初值为＿＿＿，j的初值为_____,m第一次 查找第＿＿＿＿个元素，一共比对了＿＿＿次．１６３２已知数组a中存放了13.27.31.49.55.68,现在要查找27,利用对分查找的具体过程： (1)因比较次数不定,只能用do语句,不能用for语句； (2)在do循环体中利用选择语句(if)判断是否查找成功; (3)若查找成功则输出查找结果，并提前结束循环(Exit do). (4)若查找不成功，则判断查找键在数组的前半部分还是后半部分，从而缩小范围． 对分查找算法的实现要点:对分查找算法的流程图:Dim i, ,j,m, key as integer 输入要查找的数据Key i=1:j=n Do while i<=j m=(i+j)2 if key=d(m) then 找到,输出m exit do endif if key>d(m) then i=m+1 else j=m-1 endif loop对分查找算法程序的基本框架:顺序查找与对分查找的比较:课堂练习:1、数据元素a(1)到a(8)中存储了8个整数，分别为：100、20、60、10、56、89、45、23。使用顺序查找算法查找整数300，则共需查找次数为 （ ） A. 6 B. 7 C. 8 D. 9 课堂练习:2、在数组d(1)到d(6)中存储了某一品牌电脑6个商家的报价，其数据依次为“2200、2250、2280、2300、2350、2400”。现使用对分查找数据2250，需要查找的次数是 ( ) A. 4 B. 3 C. 2 D. 1 课堂练习:3、下列问题可以使用对分查找算法解决的是 （ ） A．找回遗忘的由6位数字组成的密码 B．在一堆金币中找一枚伪装的镀金镍币 C．找出全班期末考试70至80分的同学 D．在一堆盘子中找出一个有裂痕的盘子 ? 课堂练习:4、物流公司数据库中有40000多条记录，这些记录已经按照编号作了排序，若访问一条记录所需的时间为10毫秒，则用对分查找算法检索某一条记录所需要的时间最多为 （ ） 10毫秒 B. 150毫秒 C. 160毫秒 D. 200毫秒 感谢聆听！ ... ...