资源简介

(共22张PPT)
5.4 数 据 查 找 （二）
——二 分 查 找
册 别：选择性必修1
学 科：高中信息技术（浙教版）
学习目标：
能理解二分查找的算法思想。
能合理选用数据结构，理解二分查找的范围与条件。
能用自然语言、流程图、Python语言、二叉树实现二分查找。
能熟练应用二分查找算法，解决生活、学习中的问题。
阅读教材P137-141，可根据个性学习暂停或加速播放课程。
猜一猜：
小明的计时手表多少money？
已知前提：价格20-80元？
第1次：50
高了
第2次：40
低了
第3次：45
对了
二分查找概念：
二分查找（binary search）又称折半查找，对分查找。
它是一种效率很高的查找方法，但被查找的数据序列必须是有序的。
二分查找算法思想
②如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找
③在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
①将查找键与有序数组内处于中间位置的元素进行比较；
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
1 2 3 4 5 6 7
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
1 2 3 4 5 6 7
a[0] a[1] a[2] 或 a[4] a[5] a[6]
1 2 3 5 6 7
提示：（1） 10个数据存储在d[0]到d[9] （2）Key=12
i=0
j=9
m=4
i=0
j=3
m=1
d [0]
d [1]
d [2]
d [3]
d [4]
d [5]
d [6]
d [7]
d [8]
d [9]
16
5
21
28
18
26
12
39
56
48
此时i=0，j=3，m=1时，a[m]==key，找到结束查找。
二分查找实践体验：
在数组d的10个元素中，已按升序存储了10个数据：5、12、16、18、21、26、28、39、48、56，如何用二分法查找数据12（已存储在变量key中）？
思考：
如何确定查找区间中点m的位置？
m=（i+j)//2
m=（i+j+1)//2
讨论：
查找范围（i,j）的变化情况？
将查找键key值与d[m]比较，结果必然是如下三种情况之一：
keykey=d[m] 找到了需要的数据。
key>d[m] 数组d递增，新的查找范围为【m+1，j】。
思考：若数组d递减，查找范围（i,j）如何变化？
keykey>d[m] 数组d递减，新的查找范围为【i，m-1】。
二分查找的流程图描述(升序序列中查找）：填一填
开始
i=0，j=n-1
i<=j
Y
d[m]==key
N
j←m-1
未找到，输出结果
找到，输出结果
结束
Y
N
m←i+j /2
d[m]>key
i←m+1
N
Y
（1）
（2）
二分查找规律：
keykey=d[m] 找到了需要的数据。
key>d[m] 与①相同的理由，必须在新的范围（m+1，j）中继续查找。
这样，除了出现情况②，在通过一次比较后，新的查找范围将不超过上一次查找范围的一半。
查找键key值与d[m]比较结果情况总结：
中点位置 m=（i+j)/2
二分查找Python程序实现:
d=[6,12,15,18,22,25,28,35,46,58]
key=int(input(“输入待查找元素：”)）
f=False
i = 0 # i和j定义子数组的边界，一开始搜索的是整个数组
j = len(d)-1
while i <= j:
m = (i+j) //2
if d[m] == key:
f=True
b=m
break
if key < d[m]: # 到左边去找
j = m-1
else: # 到右边去找
i = m + 1
if f==True:
print("查找成功！第"+str(b)+"个")
else:
print("没有找到！")
二分查找的递归实现:
def bsearch(k,dat,i,j):
if i>=j+1: # 递归结束条件1
print("未找到！") # 递归结束值1
return
m = (i+j) //2
if dat[m] == k: # 递归结束条件2
print("找到了！第"+str(m+1)+"个" ) # 递归结束值2
return
elif k < dat[m]: # 到左边区间去找
return bsearch(k,dat,i,m-1) # 递归表达式，自己调用自己
elif k >= dat[m]: # 到右边区间去找
return bsearch(k,dat,m+1,j) # 递归表达式，自己调用自己
#主程序
d=[6,12,15,18,22,25,28,35,46,58]
print(d)
key=int(input("输入待查找元素："))
i=0;j=len(d)-1
bsearch(key,d,i,j)#调用bsearch函数
顺序查找、二分查找对比
顺序查找 二分查找
查找对象 无要求 只可查找有序的序列
效率 低 高
最少查找次数 1 1
最多查找次数 <=n <=int(log2n)+1
平均查找次数
≈ log(n+1)-1
二分查找判定树：二叉树
i=0
j=9
m=4
i=0
j=3
m=1
d [0]
d [1]
d [2]
d [3]
d [4]
d [5]
d [6]
d [7]
d [8]
d [9]
16
5
21
28
18
26
12
39
56
48
i=5
j=9
m=7
4
i=0
j=0
m=0
i=2
m=2
j=3
i=3
j=3
m=3
1
7
0
2
5
8
3
6
9
二分查找判定树：二叉树
d [0]
d [1]
d [2]
d [3]
d [4]
d [5]
d [6]
d [7]
d [8]
d [9]
16
5
21
28
18
26
12
39
56
48
4
1
7
0
2
5
8
3
6
9
21
12
39
5
16
26
48
18
28
56
二分查找判定树：二叉排序树
找12：从根结点到待查结点的一条路径为21→12，比较次数为2次完成。
21
12
39
5
16
26
48
18
28
56
找18： 21→12→16→18，由此可知，在n个元素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1，即 log2n +1,即 <=int(log2n)+1
生活实战应用：
某校期中考试部分学生信息技术与通用技术成绩如右表所示，查询某赋分数的所有学生名单，并输出共有几个同分数的学生，要求实现以上功能，如查询不到则显示“无此分数的学生”。请编程实现。
生活实战应用：
#读取csv中的文件数据
import csv #导入csv模块
f=open("期中考技术成绩.csv",'r')#打开csv数据文件
c=[]#定义空列表a
r=csv.reader(f)#建立一个读入数据的对象r
n=0#记录数初值
for i in r:#每一行为c列表一个元素,此元素为字符串
c.append(i)#从表中第一行开始依次读入到c列表中
n+=1 #记录数增加1
f.close#关闭csv数据文件
print("从CSV中获得的数据：")
for i in range(len(c)):
print(c[i]) #输出csv文件中读入的记录
key=int(input("请输入要查找的分数："))
i=1;j=len(c)-1#查找范围索引值的左右端点值
while i<=j: #左端点i<=右端点j,继续二分查找
m=(i+j)//2 #计算中点索引值
if keyi=m+1 #在表的右区间找
else: #key>=int(c[m][2])时
j=m-1 #在表的左区间找
print("要查找的"+str(key)+"数据第一个位置是："+str(i))
b=i #记录第一个位置到b中
#找第一个key所在的位置结束
#找最后一个key所在的位置
i=1;j=len(c)-1#查找范围索引值的初值与终值
while i<=j:#左端点i<=右端点j,继续二分查找
m=(i+j)//2#计算中点索引值
if key<=int(c[m][2]):#表数据降序，
i=m+1#在表的右区间找
else:#key>int(c[m][2])时
j=m-1#在表的左区间找
print("要查找的"+str(key)+"数据最后一个位置是："+str(j))
print("总共",key,"的个数为",j-b+1,"个")
print(c[0])
for k in range(b,j+1): #输出所有key的人员信息
print(c[k])
课堂小结
二分查找
算法思想 算法描述 与顺序查找的对比
查找区间i,j,m的位置
个数、不大于、不小于问题
程序实现
查找键key值与d[m]比较
学习评价
对自己的表现进行客观的评价，并思考后续完善的方向。（3=优秀，2=一般，1=仍需加油）
评分项 自我评价
能理解二分查找算法的特点及适用范围 3 2 1
能确定查找区间i,j及中点m的位置 3 2 1
能自主学习教材并用自然语言、流程图描述顺序查找算法 3 2 1
能够用Python语言描述顺序查找算法 3 2 1
能理解查找键key值与d[m]比较的三种情况 3 2 1
能够理解二分查找的判定树 3 2 1
能够查找相同元素个数、不小于某元素位置或小于某元素位置等实际应用 3 2 1
课后作业
1.某对分查找算法的 VB 程序如下：
i = 0;j = 29
m = (i + j) // 2
while i <= j and key!=a[m]:
If key > a[m]:
i = m + 1
else:
j = m – 1
m = (i+j)// 2 # ①
数组元素 a[0]到 a[29]各不相同且按升序排列，若查找键key与a[8]相等，执行该程序段，①处语句的执行次数是
A.2 B.3 C. 4 D.5
B
课后作业
2.某校校友录登记表students_sorted.csv如右图所示，已知校友录已经按照姓名的拼音升序排序，为了快速查找某位校友，输入校友名称，输出该名字的所有校友信息，若输入的校友不在校友录登记表中，则输出“查无此人”如下图所示：
程序代码如下，请在划线处填写合适的代码语句：
import csv
#读取csv文件
with open("stu.csv", "r", encoding='gb18030') as f:
data = []
reader = csv.DictReader(f)
for row in reader:
data.append(row)
stuname = input("请输入要查找的姓名：\n")
n = len(data)
L = 0
R = n-1
while ① :
mid = (L + R) // 2
if data[mid]["stu_name"]>=stuname:
R = mid-1
elif data[mid]["stu_name"]L = mid+1
if data[L]["stu_name"] == stuname:
②
while data[start]["stu_name"] == stuname:
print( ③ )
if start==n:
break
start += 1
else:
print("查无此人")
2.①L<= R ②start = L ③data[start

展开更多......

收起↑