高中信息技术浙教版（2019）选修1 第五章　课时4　顺序查找 学案（含答案）.docxVIP

课时4顺序查找

课时目标

1.通过实例分析，理解顺序查找的基本思想，掌握使用顺序查找的一般方法。

2.能根据不同的应用场景，选择合适的数据结构，能灵活使用顺序查找算法编写程序。

1.查找(Search)

查找也称检索，计算机根据所给条件查找出____________的对象，即在存储的一批数据中寻找出一个________的数据，或者确定在该批数据内是否________这样的数据。

常见的查找算法主要有：____________和____________(也称对分查找)

2.顺序查找(SequentialSearch)

顺序查找又称线性查找，是指从顺序表的一端开始，__________________将每个元素的关键字与给定值key(查找键)进行比较。若某个元素的__________________，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。

3.顺序查找算法基本框架

假设：要查找的数据为key，n个待查找的数存放在数组d中。

for循环条件：

find＝False

foriinrange(0，n)：

ifd[i]＝＝key：#则表示找到，

#修改find的值为True，并做相应处理

iffind＝＝False：

#表示未找到

While循环实现：

i＝0

whilei＝n－1：

ifd[i]＝＝key：#则表示找到，

#修改find的值为True，并做相应处理

i＝i＋1

ifi＝＝n：

#表示未找到

4.顺序查找算法程序实现

假设：要查找的数据为key，n个待查找的数存放在数组d中，本程序找到满足条件的第一个数据就结束。

for循环条件：

find＝False

foriinrange(n)：

ifkey＝＝d[i]：

find＝True

print(″find，索引号为：″，i)

break

ifnotfind：

print(″未找到″)

while循环条件：

i＝0

whilei＝n－1：

ifkey＝＝d[i]：

print(″find，索引号为：″，i)

break

else：

i＝i＋1

ifi＝＝n：

print(″未找到″)

(1)使用for循环查找时，需要设置一个逻辑变量，表示找到与否。

(2)while顺序查找还可以写为：

i＝0

find＝False

whilei＝n－1andnotflag：

ifkey＝＝d[i]：

print(″find，索引号为：″，i)

find＝True

else：

i＝i＋1

ifi＝＝n：

print(″未找到″)

例1在数组a中存储的数据依次为“3，6，5，11，15，20，13，32”。现使用顺序查找算法在数组a中查找数据20，共需查找的次数为()

A.5次 B.6次 C.7次 D.8次

听课笔记：

变式训练在数组a中存储的数据依次为“3，6，5，11，15，20，13，32”。现使用顺序查找算法在数组a中查找数据8，共需查找的次数为()

A.0次 B.8次 C.9次 D.无穷次

例2有如下Python程序段：

d＝[3，9，1，2，6，9，0]

n＝len(d)

key＝int(input(″pleaseinputkey：″))

flag＝True

i＝0

whilei＝n－1andflag：

ifkey＝＝d[i]：

pos＝i

flag＝False

else：

i＝i＋1

ifi＝＝n：

print(″未找到″)

else：

print(″找到，索引位置：″，pos)

程序运行时，输入key的值为9，输出结果为()

A.未找到

B.找到，索引位置：1

C.找到，索引位置：5

D.找到，索引位置：15

听课笔记：

变式训练有如下Python程序段：

d＝[3，9，1，9，6，8，9]

n＝len(d)

key＝int(input(″pleaseinpu