资源简介

(共15张PPT)
5.4.1 顺序查找
查找又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一
批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数
据。若没有找到满足条件的对象，则返回特定值，表明查找失败；若查找到
满足条件的对象，则表明查找成功，一般要求返回该对象的存储位置或对象
值本身。
通常，程序将按照查找的结果（找到或未找到）来决定接着应执行后面哪一个
计算步骤。
顺序查找
顺序查找又称线性查找，从顺序表的
一端开始，依次将每个元素的关键字
与给定值key（查找键）进行比较。
若某个元素的关键字等于key，则表明
查找成功；若所有元素都比较完毕仍找
不到，则表明查找失败。
如下图所示，在规模为8的数组d中，分别按顺序查找算法寻找数据18和15
的情况，处理过程中找到的第4个数组元素d[3]中的数据与18相等，表示8个
数据中存在值为18的元素；而若key为15时，查找完所有数据仍未找到，表
示8个数据中不存在值为15的元素。
18
key
d
25 22 13 18 14 11 17 19
0 1 2 3 4 5 6 7
到此处已找到
15
key
d
25 22 13 18 14 11 17 19
0 1 2 3 4 5 6 7
查完所有数据仍未找到
顺序查找过程实例
时间复杂度为O(n)
开始
i 0
i≤n-1
d[i]=key
i i+1
是
否
找到，输出信息
未找到，输出信息
结束
顺序查找算法流程图
是
否
实现此算法的Python程序如下：
d=[25,22,13,18,14,11,17,19]
key=18
flag=False
length=len(d)
for i in range(length):
if d[i]==key:
flag=True
break
if flag=True:
print(“查找成功！”)
else:
print(“未找到”)
顺序查找算法也可以写成函数的形式，如下所示：
def seq_search(s,a):
length=len(s)
flag=False
for i in range(length):
if s[i]==a:
flag=True
break
if flag==True:
return i
else:
return False
d=[25,22,13,18,14,11,17,19]
key=15
result=seq_search(d,key)
print(result)
小结
顺序查找本质上是一种枚举算法思想，顺序查找程序就是用循环来枚举所
有要查找的对象，然后在循环体内用条件判断当前枚举出的对象是否等于
查找对象。
假设n个数据依次存储在长度为n的数组a中，查找键为key，自定义函数
seq_search(a,key)返回数组a中首个值为key的元素下标，若找不到key
则返回-1。
def seq_search(a,key):
for i in range(len(a)):
if a[i]==key:
return i
else:
return -1
练一练
1.某个列表中共有m个元素，进行顺序查找之后查找失败，则其中元素的
比较次数是（ ）
A.m B.m2 C.m-1 D.(m+1)//2
A
2.有如下python程序段：
a=[2,6,8,8,2,4,7,3]
p=0
for i in range(1,len(a)):
if a[i]>a[p]:
p=i
则运行该段代码后，变量p的值为（ ）
A.0
B.2
C.3
D.8
B
3.有如下Python程序段：
key=int(input(“key=”))
s=0
a=[]
for i in range(10):
a.append(i+1)
for i in range(len(a)):
if a[i]%key==0:
s=s+1
print(s)
当输入的key=5时，程序运行结束后，输出的值为（ ）
A.0 B.1 C.2 D.3
C
4.查找一个英文句子中是否包含某个单词，可以使用顺序查找的方法，实现
上述功能的Python程序段如下，请在划线处填入合适的代码。
long=“I have an apple and an orange.”
word=input(“输入要查找的单词：”)
flag=____________________________
for i in range(len(long)-len(word)):
if long[______________]==word:
print(“yes”)
flag=True
break
if flag==False:
print(“no”)
False
i:i+len(word)
②
①
谢 谢

展开更多......

收起↑