1、查找算法设计查找算法设计 随机产生若干个整数，使用顺序查找和对分查找进随机产生若干个整数，使用顺序查找和对分查找进行查寻数据，输出查找结果。行查寻数据，输出查找结果。新课引入新课引入 在到学习、工作和生活中我们经常需要在一系列数据在到学习、工作和生活中我们经常需要在一系列数据中查找出是否有某个特定数据，中查找出是否有某个特定数据，如在图书馆按书目查找如在图书馆按书目查找某本书，在运动会上查寻某运动员的比赛成绩，在网上搜某本书，在运动会上查寻某运动员的比赛成绩，在网上搜索信息、使用索信息、使用QQQQ查找好友等，这时就会用到查找算法了。查找好友等，这时就会用到查找算法了。问题提出问题提出 一、采
2、用何种方法进行查找？一、采用何种方法进行查找？1.1.顺序查找顺序查找顺序查找是最容易想到，也是最容易实现的一种查找算法，顺序查找是最容易想到，也是最容易实现的一种查找算法，方法是将要找的数据与数组中的每个数据从第一个开始逐方法是将要找的数据与数组中的每个数据从第一个开始逐一进行比较，直到找到或者全部找完。一进行比较，直到找到或者全部找完。（1 1）顺序查找算法流程图）顺序查找算法流程图 Private Sub Command6_Click()顺序查找顺序查找Dim i As Integer,key As Integerkey=Val(Text2.Text)查找的数据查找的数据For i=1
3、To num 依次查找依次查找If d(i)=key Then 找到了数据找到了数据Label5.Caption=在数组的第+Str(i)+个位置Exit For 中断当前中断当前ForFor循环循环End IfNextIf i=num+1 Then Label5.Caption=在数组中没有找到数在数组中没有找到数据据+Str(key)End Sub（2 2）编写程序代码）编写程序代码 二、如果数组中有二、如果数组中有n n个元素，那么顺序查找的平均查找个元素，那么顺序查找的平均查找次数是（次数是（n+1n+1）/2/2次，有没有效率更高的查找算法呢？次，有没有效率更高的查找算法呢？1.1.
4、猜数游戏猜数游戏 在猜数游戏过程，如何使用更少的次数猜对数字呢？在猜数游戏过程，如何使用更少的次数猜对数字呢？采用对半策略。第一次猜采用对半策略。第一次猜5050，结果是太小了，所以数字肯，结果是太小了，所以数字肯定在定在5151100100，第二次就猜，第二次就猜5151100100的当中位置（取下限的的当中位置（取下限的整数），猜整数），猜7575，结果是太大了，所以数字肯定在，结果是太大了，所以数字肯定在51517474，再猜当中位置再猜当中位置5757，正好猜中！这种猜数的方法就是对分查，正好猜中！这种猜数的方法就是对分查找的算法。找的算法。2.2.对分查找算法对分查找算法 首先将查找
5、键与有序数组内处于中间位置的元素进行比首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。方法进行查找，直到获得最终结果。对分查找的前提条件对分查找的前提条件数组中的数据是已经排序的。数组中的数据是已经排序的。(1)对分查找算法流程图对分查找算法流程图对分查找过程如下图所
6、示：对分查找过程如下图所示：（2）编写程序代码）编写程序代码 Private Sub Command4_Click()对分查找对分查找Dim i As Integer,j As Integer,key As Integer,m As IntegerDim nc As IntegerIf Not sorted Then 进行对分查找时，需先对数据进行排序进行对分查找时，需先对数据进行排序MsgBox 进行对分查找时，需先对数据进行排序Exit Sub 结束过程结束过程 End Ifkey=Val(Text2.Text)输入查找的数据输入查找的数据i=1j=numnc=0 查找次数查找次数ncDo
7、 While i=j 对分查找对分查找nc=nc+1m=Fix(i+j)/2)If d(m)=key Then 找到了找到了Label6.Caption=在数组的第+Str(m)+个位置，共查找了+Str(nc)+次 Exit SubEnd IfIf key d(m)Then 未找到，继续查找未找到，继续查找j=m-1Elsei=m+1End IfLoopLabel6.Caption=在数组中没有找到数据+Str(key)+，共查找了+Str(nc)+次End Sub 使用对分查找，每次都把规模缩小一半，效率比顺序使用对分查找，每次都把规模缩小一半，效率比顺序查找要高，但在进行对分查找前，需要
8、将它排好序。查找要高，但在进行对分查找前，需要将它排好序。（3 3）运行调试程序）运行调试程序 根据算法流程图根据算法流程图,填空完善已经设计好的界面和部分填空完善已经设计好的界面和部分代码的顺序查找和对分查找算法，并进行调试。代码的顺序查找和对分查找算法，并进行调试。课堂练习课堂练习1.一个数组中含有元素一个数组中含有元素A、B、C、D、E、F、G、H、I、J、K、L、M、N应用对分查找算法，查找目标为应用对分查找算法，查找目标为J时，会查时，会查经哪几个字母，如果查找的是经哪几个字母，如果查找的是Z呢？呢？参考答案：参考答案：使用对分查找，查找目录使用对分查找，查找目录J J时，会查经时，
9、会查经H H、L L，查找，查找Z Z，会查经会查经H H、L L、N N，最后查找，最后查找z z未找到。未找到。2.数组元素为：数组元素为：Alice、Byron、Duane、Elaine、Floyd、Gene、Herry、Iris，请回答：请回答：哪个查找算法（顺序查找和对分查找）能比较快找到名哪个查找算法（顺序查找和对分查找）能比较快找到名字字Gene?哪个查找算法（顺序查找和对分查找）能比较快找到名哪个查找算法（顺序查找和对分查找）能比较快找到名字字Alice?哪个查找算法（顺序查找和对分查找）能比较快地测定哪个查找算法（顺序查找和对分查找）能比较快地测定名字名字Bruce不存在不存
10、在?哪个查找算法（顺序查找和对分查找）能比较快地测定哪个查找算法（顺序查找和对分查找）能比较快地测定名字名字Sue不存在不存在?当利用顺序查找算法查找名字当利用顺序查找算法查找名字Floyd时，查问了多少个数时，查问了多少个数据？使用对分查找算法时，又要查问多少个数据？据？使用对分查找算法时，又要查问多少个数据？参考答案：参考答案：查找查找GeneGene：对分查找快，对分查找：对分查找快，对分查找3 3次，顺序查找次，顺序查找6 6次次查找查找 AliceAlice：顺序查找快，顺序查找：顺序查找快，顺序查找1 1次，对分查找次，对分查找4 4次次查找查找 BruceBruce：对分查找快，
11、对分查找：对分查找快，对分查找4 4次，顺序查找次，顺序查找8 8次次查找查找 SueSue：对分查找快，对分查找：对分查找快，对分查找4 4次，顺序查找次，顺序查找8 8次次使用顺序查找使用顺序查找FloydFloyd，查找了，查找了5 5个数据，使用对分查找，个数据，使用对分查找，查问了查问了1 1个数据个数据3.3.对于有对于有50005000个元素的数组，使用对分查找，最多查问多少个个元素的数组，使用对分查找，最多查问多少个数据？使用顺序查找呢？试比较两种查找算法的效率。数据？使用顺序查找呢？试比较两种查找算法的效率。参考答案：参考答案：使用对分查找最多查问使用对分查找最多查问log2
12、5001log25001个数据，使用顺序查找个数据，使用顺序查找最多查问最多查问50005000次，所以对分查找效率比较高。次，所以对分查找效率比较高。4.4.验血问题的算法。有万大军三天后将要出发作战。验血问题的算法。有万大军三天后将要出发作战。军医发现有一位士兵带入了一种传染病菌，三天后发作军医发现有一位士兵带入了一种传染病菌，三天后发作将传染给全军，使部队丧失作战能力，只有通过验血才将传染给全军，使部队丧失作战能力，只有通过验血才能发现谁是患者。但当时军医每天至多只能检验能发现谁是患者。但当时军医每天至多只能检验份血样，如果逐一地进行化验需要天，这将贻份血样，如果逐一地进行化验需要天，这
13、将贻误战机。要求设计一个算法，帮助军医解决上述问题。误战机。要求设计一个算法，帮助军医解决上述问题。参考答案：参考答案：第一天，将第一天，将1010万人分成万人分成100100组，每组组，每组10001000人，滴血于一处，人，滴血于一处，成为一份血样，总共有成为一份血样，总共有100100份血样，对这份血样，对这100100份血样进行验血，查份血样进行验血，查出带菌血样所在组出带菌血样所在组A A；第二天，将有带菌血样所在组第二天，将有带菌血样所在组A A的的10001000人分成人分成100100组，每组组，每组1010人，滴血于一处，成为一份血样，总共有人，滴血于一处，成为一份血样，总共
14、有100100份血样，对这份血样，对这100100份份血样进行验血，查出带菌血样所在组血样进行验血，查出带菌血样所在组B B；第三天，将有带菌血样所在组第三天，将有带菌血样所在组B B的的1010人分成人分成1010组，每组组，每组1 1人，人，滴血于一处，成为一份血样，总共有滴血于一处，成为一份血样，总共有1010份血样，对这份血样，对这1010份血样进份血样进行验血，查出带菌血样所在组行验血，查出带菌血样所在组C C，即找到带有传染病毒的士兵；，即找到带有传染病毒的士兵；5.进行对分查找算法的前提是进行对分查找算法的前提是:(A)被查找数据元素个数是奇数被查找数据元素个数是奇数 (B)被查
15、找数据元素个数是偶数被查找数据元素个数是偶数 (C)被查找数据元素是有序的被查找数据元素是有序的 (D)被查找数据元素是无序的被查找数据元素是无序的 参考答案：参考答案：C 6.用对分查找法从数列用对分查找法从数列3，6，7，10，12，16，25，30，75中找到数据中找到数据10的最少查找次数是的最少查找次数是:(A)2 (B)3 (C)4 (D)7 参考答案：参考答案：B 7.应用对分查找算法查找一个有应用对分查找算法查找一个有200个表项的列表时，个表项的列表时，必须查问的表项数目至多有几个？如果列表中有必须查问的表项数目至多有几个？如果列表中有10万个表项又怎样？万个表项又怎样？参考答案：参考答案：8个，个，17个个谢谢 谢！谢！
