粤教版高中信息技术选修1算法与程序设计：查找算法设计课件

查找算法设计查找算法设计1随机产生若干个整数，使用顺序查找和对分查找进行查寻数据，输出查找结果。

随机产生若干个整数，使用顺序查找和对2新课引入

在到学习、工作和生活中我们经常需要在一系列数据中查找出是否有某个特定数据，如在图书馆按书目查找某本书，在运动会上查寻某运动员的比赛成绩，在网上搜索信息、使用QQ查找好友等，这时就会用到查找算法了。

新课引入在到学习、工作和生活中我们经常需要在3问题提出

一、采用何种方法进行查找？

1.顺序查找

顺序查找是最容易想到，也是最容易实现的一种查找算法，方法是将要找的数据与数组中的每个数据从第一个开始逐一进行比较，直到找到或者全部找完。

问题提出一、采用何种方法进行查找？

1.顺序查找

顺序查找4（1）顺序查找算法流程图（1）顺序查找算法流程图5PrivateSubCommand6_Click()'顺序查找

DimiAsInteger,keyAsInteger

key=Val(Text2.Text)'查找的数据

Fori=1Tonum'依次查找

Ifd(i)=keyThen'找到了数据

Label5.Caption="在数组的第"+Str(i)+"个位置"

ExitFor'中断当前For循环

EndIf

Next

Ifi=num+1ThenLabel5.Caption="在数组中没有找到数据"+Str(key)

EndSub

（2）编写程序代码PrivateSubCommand6_Click()6二、如果数组中有n个元素，那么顺序查找的平均查找次数是（n+1）/2次，有没有效率更高的查找算法呢？

1.猜数游戏

二、如果数组中有n个元素，那么顺序查找的平均查找次数是（7

在猜数游戏过程，如何使用更少的次数猜对数字呢？采用对半策略。第一次猜50，结果是太小了，所以数字肯定在51～100，第二次就猜51～100的当中位置（取下限的整数），猜75，结果是太大了，所以数字肯定在51～74，再猜当中位置57，正好猜中！这种猜数的方法就是对分查找的算法。在猜数游戏过程，如何使用更少的次数猜对数82.对分查找算法首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。对分查找的前提条件数组中的数据是已经排序的。2.对分查找算法9(1)对分查找算法流程图(1)对分查找算法流程图10对分查找过程如下图所示：对分查找过程如下图所示：11（2）编写程序代码PrivateSubCommand4_Click()'对分查找

DimiAsInteger,jAsInteger,keyAsInteger,mAsInteger

DimncAsInteger

IfNotsortedThen'进行对分查找时，需先对数据进行排序

MsgBox"进行对分查找时，需先对数据进行排序"

ExitSub'结束过程

EndIf

key=Val(Text2.Text)'输入查找的数据

i=1

j=num

nc=0'查找次数nc

DoWhilei<=j'对分查找

nc=nc+1

m=Fix((i+j)/2)

Ifd(m)=keyThen‘找到了

Label6.Caption="在数组的第"+Str(m)+"个位置，共查找了"+Str(nc)+"次"

ExitSub

EndIf

Ifkey<d(m)Then'未找到，继续查找

j=m-1

Else

i=m+1

EndIf

Loop

Label6.Caption="在数组中没有找到数据"+Str(key)+"，共查找了"+Str(nc)+"次"

EndSub

（2）编写程序代码PrivateSubCom12

使用对分查找，每次都把规模缩小一半，效率比顺序查找要高，但在进行对分查找前，需要将它排好序。

（3）运行调试程序

根据算法流程图,填空完善已经设计好的界面和部分代码的顺序查找和对分查找算法，并进行调试。使用对分查找，每次都把规模缩小一半，效率比顺13课堂练习1.一个数组中含有元素A、B、C、D、E、F、G、H、I、J、K、L、M、N应用对分查找算法，查找目标为J时，会查经哪几个字母，如果查找的是Z呢？参考答案：

使用对分查找，查找目录J时，会查经H、L，查找Z，会查经H、L、N，最后查找z未找到。

课堂练习1.一个数组中含有元素A、B、C、D、E、F、G、H142.数组元素为：Alice、Byron、Duane、Elaine、Floyd、Gene、Herry、Iris，请回答：

①哪个查找算法（顺序查找和对分查找）能比较快找到名字Gene?

②哪个查找算法（顺序查找和对分查找）能比较快找到名字Alice?

③哪个查找算法（顺序查找和对分查找）能比较快地测定名字Bruce不存在?

④哪个查找算法（顺序查找和对分查找）能比较快地测定名字Sue不存在?

⑤当利用顺序查找算法查找名字Floyd时，查问了多少个数据？使用对分查找算法时，又要查问多少个数据？

2.数组元素为：Alice、Byron、Duane、Elai15参考答案：①查找Gene：对分查找快，对分查找3次，顺序查找6次②查找Alice：顺序查找快，顺序查找1次，对分查找4次③查找Bruce：对分查找快，对分查找4次，顺序查找8次④查找Sue：对分查找快，对分查找4次，顺序查找8次⑤使用顺序查找Floyd，查找了5个数据，使用对分查找，查问了1个数据

参考答案：①查找Gene：对分查找快，对分查找3次，顺序查找163.对于有5000个元素的数组，使用对分查找，最多查问多少个数据？使用顺序查找呢？试比较两种查找算法的效率。

参考答案：

使用对分查找最多查问log25001个数据，使用顺序查找最多查问5000次，所以对分查找效率比较高。

3.对于有5000个元素的数组，使用对分查找，最多查问多少个174.验血问题的算法。有１０万大军三天后将要出发作战。军医发现有一位士兵带入了一种传染病菌，三天后发作将传染给全军，使部队丧失作战能力，只有通过验血才能发现谁是患者。但当时军医每天至多只能检验１００份血样，如果逐一地进行化验需要１０００天，这将贻误战机。要求设计一个算法，帮助军医解决上述问题。4.验血问题的算法。有１０万大军三天后将要出发作战。军医发现18参考答案：

第一天，将10万人分成100组，每组1000人，滴血于一处，成为一份血样，总共有100份血样，对这100份血样进行验血，查出带菌血样所在组A；第二天，将有带菌血样所在组A的1000人分成100组，每组10人，滴血于一处，成为一份血样，总共有100份血样，对这100份血样进行验血，查出带菌血样所在组B；第三天，将有带菌血样所在组B的10人分成10组，每组1人，滴血于一处，成为一份血样，总共有10份血样，对这10份血样进行验血，查出带菌血样所在组C，即找到带有传染病毒的士兵；

参考答案：19进行对分查找算法的前提是:(A)被查找数据元素个数是奇数

(B)被查找数据元素个数是偶数

(C)被查找数据元素是有序的

(D)被查找数据元素是无序的

参考答案：C进行对分查找算法的前提是:206.用对分查找法从数列3，6，7，10，12，16，25，30，75中找到数据10的最少查找次数是:(A)2(B)3(C)4(D)7

参考答案：B6.用对分查找法从数列3，6，7，10，12，16，25217.应用对分查找算法查找一个有200个表项的列表时，必须查问的表项数目至多有几个？如果列表中有10万个表项又怎样？参考答案：8个，17个

7.应用对分查找算法查找一个有200个表项的列表时，22谢谢！谢谢！23查找算法设计查找算法设计24随机产生若干个整数，使用顺序查找和对分查找进行查寻数据，输出查找结果。

随机产生若干个整数，使用顺序查找和对25新课引入

在到学习、工作和生活中我们经常需要在一系列数据中查找出是否有某个特定数据，如在图书馆按书目查找某本书，在运动会上查寻某运动员的比赛成绩，在网上搜索信息、使用QQ查找好友等，这时就会用到查找算法了。

新课引入在到学习、工作和生活中我们经常需要在26问题提出

一、采用何种方法进行查找？

1.顺序查找

顺序查找是最容易想到，也是最容易实现的一种查找算法，方法是将要找的数据与数组中的每个数据从第一个开始逐一进行比较，直到找到或者全部找完。

问题提出一、采用何种方法进行查找？

1.顺序查找

顺序查找27（1）顺序查找算法流程图（1）顺序查找算法流程图28PrivateSubCommand6_Click()'顺序查找

DimiAsInteger,keyAsInteger

key=Val(Text2.Text)'查找的数据

Fori=1Tonum'依次查找

Ifd(i)=keyThen'找到了数据

Label5.Caption="在数组的第"+Str(i)+"个位置"

ExitFor'中断当前For循环

EndIf

Next

Ifi=num+1ThenLabel5.Caption="在数组中没有找到数据"+Str(key)

EndSub

（2）编写程序代码PrivateSubCommand6_Click()29二、如果数组中有n个元素，那么顺序查找的平均查找次数是（n+1）/2次，有没有效率更高的查找算法呢？

1.猜数游戏

二、如果数组中有n个元素，那么顺序查找的平均查找次数是（30

在猜数游戏过程，如何使用更少的次数猜对数字呢？采用对半策略。第一次猜50，结果是太小了，所以数字肯定在51～100，第二次就猜51～100的当中位置（取下限的整数），猜75，结果是太大了，所以数字肯定在51～74，再猜当中位置57，正好猜中！这种猜数的方法就是对分查找的算法。在猜数游戏过程，如何使用更少的次数猜对数312.对分查找算法首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。对分查找的前提条件数组中的数据是已经排序的。2.对分查找算法32(1)对分查找算法流程图(1)对分查找算法流程图33对分查找过程如下图所示：对分查找过程如下图所示：34（2）编写程序代码PrivateSubCommand4_Click()'对分查找

DimiAsInteger,jAsInteger,keyAsInteger,mAsInteger

DimncAsInteger

IfNotsortedThen'进行对分查找时，需先对数据进行排序

MsgBox"进行对分查找时，需先对数据进行排序"

ExitSub'结束过程

EndIf

key=Val(Text2.Text)'输入查找的数据

i=1

j=num

nc=0'查找次数nc

DoWhilei<=j'对分查找

nc=nc+1

m=Fix((i+j)/2)

Ifd(m)=keyThen‘找到了

Label6.Caption="在数组的第"+Str(m)+"个位置，共查找了"+Str(nc)+"次"

ExitSub

EndIf

Ifkey<d(m)Then'未找到，继续查找

j=m-1

Else

i=m+1

EndIf

Loop

Label6.Caption="在数组中没有找到数据"+Str(key)+"，共查找了"+Str(nc)+"次"

EndSub

（2）编写程序代码PrivateSubCom35

使用对分查找，每次都把规模缩小一半，效率比顺序查找要高，但在进行对分查找前，需要将它排好序。

（3）运行调试程序

根据算法流程图,填空完善已经设计好的界面和部分代码的顺序查找和对分查找算法，并进行调试。使用对分查找，每次都把规模缩小一半，效率比顺36课堂练习1.一个数组中含有元素A、B、C、D、E、F、G、H、I、J、K、L、M、N应用对分查找算法，查找目标为J时，会查经哪几个字母，如果查找的是Z呢？参考答案：

使用对分查找，查找目录J时，会查经H、L，查找Z，会查经H、L、N，最后查找z未找到。

课堂练习1.一个数组中含有元素A、B、C、D、E、F、G、H372.数组元素为：Alice、Byron、Duane、Elaine、Floyd、Gene、Herry、Iris，请回答：

①哪个查找算法（顺序查找和对分查找）能比较快找到名字Gene?

②哪个查找算法（顺序查找和对分查找）能比较快找到名字Alice?

③哪个查找算法（顺序查找和对分查找）能比较快地测定名字Bruce不存在?

④哪个查找算法（顺序查找和对分查找）能比较快地测定名字Sue不存在?

⑤当利用顺序查找算法查找名字Floyd时，查问了多少个数据？使用对分查找算法时，又要查问多少个数据？

2.数组元素为：Alice、Byron、Duane、Elai38参考答案：①查找Gene：对分查找快，对分查找3次，顺序查找6次②查找Alice：顺序查找快，顺序查找1次，对分查找4次③查找Bruce：对分查找快，对分查找4次，顺序查找8次④查找Sue：对分查找快，对分查找4次，顺序查找8次⑤使用顺序查找Floyd，查找了5个数据，使用对分查找，查问了1个数据

参考答案：①查找Gene：对分查找快，对分查找3次，顺序查找393.对于有5000个元素的数组，使用对分查找，最多查问多少个数据？使用顺序查找呢？试比较两种查找算法的效率。

参考答案：

使用对分查找最多查问log25001个数据，使用顺序查找最多查问5000次，所以对分查找效率比较高。

3.对于有5000个元素的数组，使用对分查找，最多查问多少个404.验血问题的算法。有１０万大军三天后将要出发作战。军医发现有一位士兵带入了一种传染病菌，三天后发作将传染给全军，使部队丧失作战能力，只有通过验血才能发现谁是患者。