资源简介

(共27张PPT)
5.4数据查找
顺序查找
二分查找
查找又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。通常，程序将按照查找的结果（找到或未找到）来决定接着应执行后面哪一个计算步骤。
你能在上图中找到那个特别的数字3吗？
顺序查找
算法思想
顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。
若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。
①算法简单，对数据是否有序没有要求。
②查找效率较低，当数据量大时不宜使用。
算法特点
顺序查找
以“在成绩系统中查找某学号”为例，假定某学习小组8名学生的学号数据存储在数组d中，要查找的学生学号（查找键）已经存储在变量key中。
0 1 2 3 4 5 6 7
d 25 22 13 18 14 11 17 19
key 18
0 1 2 3 4 5 6 7
d 25 22 13 18 14 11 17 19
key 15
找到
未找到
你能在上图中找到那个特别的数字3吗？
顺序查找
将待查找数据存储于数组d中要查询的数据存储于变量key中
②依次将每个元素与key比较
③若某个关键字等于键值则查找成功； 所有元素比较完毕仍找不到，则查找失败
顺序查找
将待查找数据存储于数组d中要查询的数据存储于变量key中
②依次将每个元素与key比较
③若某个关键字等于键值则查找成功； 所有元素比较完毕仍找不到，则查找失败
#读取数据按行存储到数组d中
#d=[“555555...”,“555555...”,...]
flag=False
for i in range(len(d)):#遍历每一行
for j in range(__________):#遍历每一列
if :
print("3在第%d行,第%d列"%(i+1,j+1))
flag=True
break
if :
print("不存在特殊字符")
d[i][j]==”3”
flag==False
len(d[i])
枚举算法
顺序查找
小结
1.顺序查找本质上是一种__________思想，顺序查找程序就是用循环来枚举所有要查找的对象，然后在循环体内用条件判断当前枚举出的对象是否等于查找对象。
2.一般情况是，当需要查找的数据规模为 n 时，顺序查找最少查找____ 次，最多查找_____次，其平均查找次数是________。
3.顺序查找最大的优点是查找的数据可以是乱序的，但是其缺点是查找效率太低。顺序查找将待查找的数值与序列中的数逐个进行比较，直到找出与给定数值相同的数为止，其时间复杂度为_____ 。
枚举算法
1
n
(1+n)/2
O(n)
二分查找
算法思想
二分查找又称折半查找，对分查找。它是一种效率很高的查找算法，但被查找的数据序列必须是有序的。
首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。
算法特点
①要求被查找数据必须有序。
②查找效率高，适用于大数据查找。
6 12 15 18 22 25 28 35 46 58 60
6 12 15 18 22 25 28 35 46 58 60
6 12 15 18 22 25 28 35 46 58 60
6 12 15 18 22 25 28 35 46 58 60
6 12 15 18 22 25 28 35 46 58 60
二分查找
i
j
mid
Key=12
开始：
第1遍查找：
第2遍查找：
第3遍查找：
第4遍查找：
i
j
0 1 2 3 4 5 6 7 8 9 10
i
j
mid
i
j
mid
i
j
mid
二分查找
算法演算
（1）key与d[mid]的大小比较影响下一次查找的范围[i,j]。
①若d[mid]②若d[mid]>key，则查找前半段：i=________，j=______
（2）继续重复进行查找的条件。
当i<=j时
（3）对分查找最多的查找次数(n个数据)。
最多次数=int(log2n)+1
∵n个数据对分x次最后变为1个数据
∴n/2**x=1
∴x=log2n
∵最后一个数据还要参与一次查找
∴最多次数=int(log2n)+1
mid+1
j
i
mid-1
二分查找
①存储待查找数据key等
key=12;f=False
d=[6,12,15,18,22,25,28,35,46,58,60]
②i和j定义子数组的边界
i=0;j=len(d)-1
当存在待查找的子数组时，继续查找
③确定本次查找的数据下标
本次查找的数据下标为i,j的中点
④若找到则停止循环，记录位置
判断中点数据是否为key值：
找到记录下标;做找到标记
break
没找到时，若中点数据偏大：
key应在中点左侧
没找到时，若中点数据偏小：
key应在中点右侧
⑤调整子数组范围继续查找
if f==True:
print("查找成功！第"+str(b+1)+"个数据")
else:
print("没有找到！")
⑥输出查找结果
二分查找
key=12;f=False
d=[6,12,15,18,22,25,28,35,46,58,60]
i=0;j=len(d)-1
当存在待查找的子数组时，继续查找
本次查找的数据下标为i,j的中点
判断中点数据是否为key值：
找到记录下标;做找到标记
break
没找到时，若中点数据偏大：
key应在中点左侧
没找到时，若中点数据偏小：
key应在中点右侧
if f==True:
print("查找成功！第"+str(b+1)+"个数据")
else:
print("没有找到！")
key=12; f=False
d=[6,12,15,18,22,25,28,35,46,58,60]
i=0;j=len(d)-1
while :
m=(i+j)//2
if d[m]==key:
f=True;b=m
break
if :
j=m-1
else:
_________
if f==True:
print("查找成功！第"+str(b+1)+"个数据")
else:
print("没有找到！")
i<=j
keyi=m+1
二分查找
def bsearch(s,array):
if ____________:
print("未找到")
return False
mid=(len(array)-1)//2
if :
print("找到了")
return True
elif sreturn bsearch(s,array[:mid])
else:
return __________________
key=12
d=[6,12,15,18,22,25,28,35,46,58,60]
print(bsearch(key,d))
len(array)==0
array[mid]==s
bsearch(s,array[mid+1:])
二分查找过程中的每一次判断都是将需要查找的值和数组的中间值进行不断的比较，直到找到或找遍整个序列。因此，二分查找算法可利用递归来实现。
查找算法小结
查找算法 顺序查找 二分查找
优点 ①算法简单，对数据是否有序没有要求。 ②查找效率高，适用于大数据查找。
缺点 ②查找效率较低，当数据量大时不宜使用。 ①要求被查找数据必须有序。
查找次数 一般情况是，当需要查找的数据规模为 n 时，顺序查找最少查找____次，最多查找____次，其平均查找次数是________。 无论是否找到，最多进行_____________次查找。
算法思想 顺序查找本质上是一种_______算法思想。 二分查找思想符合_______算法的思想。
时间复杂度
1
n
(1+n)/2
int(log2n)+1
枚举
递归
O(n)
O(log2n)
二叉排序树
从根结点到待查结点的一条路径为25→15→6→12，比较次数为4次。通过观察可知，在n个元素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1，即
int(log2n)+1
二叉排序树
二叉排序树：
①若左子树不为空，则左子树的值均小于它的根节点的值
②若右子树不为空，则右子树的值均大于它的根节点的值
③它的左右子树也分别为二叉排序树
记录关键字排列的有序表：[1,16,24,35,47,59,62,73,88,99]。采用二分查找，画出判定树，并给出查找关键字24的记录过程。写出该判定树的后序遍历结果。
47-16-24
课堂练习
47
16
73
1
24
88
99
59
62
35
1-35-24-16-62-59-99-88-73-47
（ ）1.某Python 程序如下，当输入不同的 key 值，运行该程序段后，n 的值可能有
A.5种 B.6种 C.7种 .8种
a=[86,75,58,46,20,18,12,5]
key=int(input())
n=0;i=0;j=len(a)-1
while i<=j:
m=(i+j)//2
if key>a[m]:
j=m-1;n=n-1
else:
i=m+1;n=n+1
A
课堂练习
1、某数组有10个元素，依次为5，12，16，23，27，30，35，41，49，50，下列选项中正确的是（ ）
A、使用对分查找査找数据12，需要的查找次数是3次
B、使用顺序查找査找数据60，需要的查找次数是10次
C、使用对分查找查找数据41，需要的查找次数是2次
D、使用顺序查找查找数据5，需要的查找次数是0次
C
课堂练习
2.有如下自定义函数调用语句print(fun([5,4,7,1,4,3,7,9],4))后,程序输出的结果为( )
def fun(a,key):
n=len(a)
i=0
while iif a[i]==key:
break
i+=1
if i==n:
i=-1
return i
A.-1 B.1 C.2 D.4
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. 某二分查找算法的程序如下：
i＝0
j＝7
n＝0
while i<＝ j ：
n＝n＋1
m＝(i ＋ j)//2
if key＝＝d[m]：
break
elif key > d[m]：
j＝m－1
else：
i＝m＋1
数组元素d[0]到d[7]的值依次为″83，75，62，41，33，27，16，2″，若运行该程序段后，n的值为2，则key的值可能是(　　)
A.62或16 B.62或27 C.75或27 D.75或16
C
5.有如下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
6、某对分查找算法的Python程序段如下：
a=[8, 17, 24, 30, 36, 40, 55, 58, 61, 66]
L, R=0, 9；s=[]
key=int(input("请输入要查找的数据："))
while L<=R:
m=(L+R+1)//2
if a[m]==key:
break
elif a[m]>key:
R=m-1
else:
L=m+1
s. append(a[m])
print(s)
执行该程序段，当输入的值为30时，程序输出的结果是（ ）
A、[40, 24] B、[40, 24, 36] C、[24, 36] D、[36, 17, 24]
B
7、有如下Python程序段：
li=[12, 18, 43, 5, 3, 21, 43, 75, 23, 54, 13, 45]
key=int(input("输入要查找的值："))
i=0
while （1） :
if （2） :
print(f"位于列表中第{i+1}个位置")
break
else:
i=i+1
else:
print("不在该列表内")
上述程序段中划线处可选语句为：
①li[i]!=key ②li[i]==key ③key in li ④i>=len(li)
则（1）（2）处语句依次应为（ ）
A、①④ B、②③ C、③② D、④②
C
8、某对分查找算法的VB程序段如下：
i=1;j=10;c=0
key=int(input())
while i<=j:
m=(i + j) //2
c+=1
If key < a[m] :
j=m – 1
Else:
i = m + 1
print(j)
列表a的值依次是[1，5，5，7，9，9，9，11，16，18]，下列说法错误的是（ ）
A、输入10，程序运行后输出7
B、程序运行后，a[i]的值可能等于key
C、程序的功能是找到列表中最后一个小于等于key的元素所在的位置
D、对于不同的输入值，程序运行后c的值一定大于2
B
谢谢

展开更多......

收起↑