浙教版信息技术选修1 2.4 查找 课件（20张ppt）

查找算法
小明身高1米70，现有身高不相等的九名学生，老师要求小明找出与自己身高一样的哪位同学！
请你利用查找算法帮小明解决这个问题
方法一：
1
2
3
4
5
6
7
8
9
顺序查找
顺序查找
是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较。若某个数据和给定的值相等，则查找成功，找到所查数据的位置；反之，查找不成功。
所有可能数据的列举
判断是否是给定的值
循环结构
选择结构
所有身高都存储在数组d中，若找到相同的身高则在文本
框text1中输出是第几位同学，若没找到在text1中则显示“不
存在该同学”，请你编写一段顺序查找语句来实现查找过程
For i ＝ to
Next I
If i＝10 then
If d(i)=1.70 then
text1.text=“第”&str(i)&”位”
exit for
End if
1
9
text1.text=“不存在该同学”
For i = 1 To n
If d(i) = Key Then
‘输出值
Exit For
End If
Next i
If i = n + 1 Then
‘输出提示语句
End If
End Sub
…
i=1
x=Val(text1.text)
p=false
Do while i < 11 and not p
if a(i)=x then
_________
pos=i
end if
i=i+1
Loop
....
P=true
例题：
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1、找出中间的一位同学：
m＝（1+9）\2
结论：小明身高大于5号同学
6
7
8
9
2、找出剩余学生中中间的一位同学：
m＝（6+9）\2
结论：小明身高等于7号同学
对分查找
对分查找的前提是数据已经有序（以递增为例），然后把待查找的数据与数组中间位置的数比较，如果比中间位置的数大，在数组的后半部分继续查找，否则在数组的前半部分查找，继续对分查找，直到找到待查找的数在数组中的位置或数组已无法对分
所有身高都存储在数组d中，若找到相同的身高则在标签
label1中输出是第几位同学，若没找到在label1中则显示“不
存在该同学”，请你编写一段对分查找语句来实现查找过程
d(1)
d(2)
d(3)
d(4)
d(5)
d(6)
d(7)
d(8)
d(9)
m：中间数组元素的下标
m＝（第一个元素下标＋最后一个元素下标）\2
i
j
m＝（i＋j）\2
m＝int（（i＋j）／2）
m＝fix（（i＋j）／2）
不存在该同学
开始
I←1 ，j←9
找到，输出结果：m
结束
N
Y
d(m)=key?
D(m)i←m+1
Y
Y
N
N
i<=j？
m← (i+j)\2
j←m-1
n
Key = Val(Text2.Text)
i = 1
j = 9
Do While

If d(M) = Key Then
Label1.Caption = “第 ” + Str(M) + “ 位"
Exit do
End If
If d(M) < Key Then

Else
End If
Loop
If i>j then
m = (i + j) \ 2
i = m + 1
j=m-1
Label1.Caption = “不存在该同学”
i<= j
例题
用对分查找从数列3、6、7、10、12、16、25、30、75中查找数据10，则依次访问的数据为（ ）
A.12、6、7、10
B.12、7、10
C.12、6、10
D.12、7、6、10
例题
某中学2009年下半年和2010年上半年各有300名和100名学生参加信息技术高考，下列VB程序用于统计参加过这两次考试的学生信息，其中command1_ click过程的算法流程图如下所示。
Private sub form_load()
‘将参加2009年下半年考试学生的身份证号码放在数组a中
‘将参加2009年下半年考试学生的身份证号码放在数组b中
‘将数组a中的数据升序排列
‘ 将数组a和数组b中的数据分别显示在列表框list1和list2中
‘代码略
End sub
Private sub command1_click()
dim I as integer,bot as integer,top as integer,m as integer
for i=1 to 300
bot =1:top=300
do while bot <= top
m=fix((bot+top)/2)
if a(m)=b(i) then
list3.additem a(m):exit do
elseif a(m)>d(i) then
m=bot-1
else
bot=m+1
end if
loop
next I
End sub
(1)该程序段所采用的查找算法名称？
(2)该程序段加框处有误，请改正？
For i＝1 to 100
Top＝m－1
比较
顺序查找是一种基本、简单的查找算法，但查找的效率往往过低；
对分查找时每次都把查找范围缩小一半
对分查找算法数据次数较少，效率较高，但它要求数组中的数据是有序的。
顺序查找与对分查找比较
是否需要
事先排序
最多查找次数
顺序查找
对分查找
不需要
需要
N
多
Log2n
少