资源简介

(共17张PPT)
数据查找
选修一：数据结构
查找
顺序查找
顺序查找
顺序查找， 叫“线性查找”，通常 于线性表
。
算法思想：从头到 尾 挨个找（或者反过来也OK）
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
找到
未找到
顺序查找程序实现
def seq_search(s,a):
length=len(s)
flag=False
for i in range(0,length):
if s[i]==a:
flag=True
break
if flag==True:
return i
else:
return False
二分查找
二分查找
0 1 2 3 4 5 6 7 8
d 7 10 13 16 19 29 32 33 37
High=len(d)-1
low=0
mid=（low+high）/2
key 29
29>mid，所以只能在右边查找
low=mid+1
二分查找又称折半查找，仅适用于有序表
二分查找
0 1 2 3 4 5 6 7 8
d 7 10 13 16 19 29 32 33 37
High
low
mid=（low+high）/2
key 29
29high=mid-1
二分查找又称折半查找，仅适用于有序表
二分查找
0 1 2 3 4 5 6 7 8
d 7 10 13 16 19 29 32 33 37
High
low
key 29
二分查找又称折半查找，仅适用于有序表
mid=（low+high）/2
29=mid，查找成功
二分查找
0 1 2 3 4 5 6 7 8
d 7 10 13 16 19 29 32 33 37
High=len(d)-1
low=0
mid=（low+high）/2
key 12
12high=mid-1
二分查找又称折半查找，仅适用于有序表
二分查找
0 1 2 3 4 5 6 7 8
d 7 10 13 16 19 29 32 33 37
High
low
mid=（low+high）/2
key 12
12>mid，所以只能在右边查找
low=mid+1
二分查找又称折半查找，仅适用于有序表
二分查找
0 1 2 3 4 5 6 7 8
d 7 10 13 16 19 29 32 33 37
High
low
mid=（low+high）/2
key 12
12high=mid-1
二分查找又称折半查找，仅适用于有序表
二分查找
0 1 2 3 4 5 6 7 8
d 7 10 13 16 19 29 32 33 37
high
low
key 12
low>high，查找失败
二分查找又称折半查找，仅适用于有序表
二分查找程序实现
s=[1,3,7,12,23,45,60]
key=23
flag=False
low=0
high=len(s)-1
while low<=high:
mid=(low+high)//2
if s[mid]==key:
n=mid
flag=True
break
elif s[mid]>key:
high=mid-1
else:
low=mid+1
if flag:
print("该元素在列表中的下标为{}".format(n))
else:
print("未找到该元素")
0 1 2 3 4 5 6 7 8 9 10
7
10
37
33
32
29
19
13
16
41
43
29
mid
mid
mid
13
37
mid
mid
mid
mid
7
16
32
41
二分查找判定树的构造
比较次数不超过判定树的高度+1
时间复杂度：log2n
二叉排序树
二叉排序树：
①若左子树不为空，则左子树的值均小于它的根节点的值
②若右子树不为空，则右子树的值均大于它的根节点的值
③它的左右子树也分别为二叉排序树
感谢大家聆听

展开更多......

收起↑