中小学教育资源及组卷应用平台
项目九 实现查找指定商品
——查找算法的应用及数据结构的选择
第二课时 体验使用二分查找法查找商品
教材分析
本节的主要内容是体验使用二分查找法查找商品。在学习中，学生将体验使用二分查找法查找对应价格的商品数据。本项目的学习强调引导学生对实际问题从数据量大小、运行时间、存储空间和算法实现难易度等方面进行综合考虑，选择恰当的查找算法，使用合适的存储结构,通过编程实现问题的解决。在体验使用二分查找法查找商品的过程中,分别采用迭代法和递归法来完成算法设计，进一步提升计算思维。索引查找法虽然有一定难度，但是有助于学生进一步认识算法与数据结构的关系，从而进一步提升计算思维。
教学目标
1.掌握常用的数据查找方法——二分查找法；
2.理解迭代概念。
3.理解递归概念。
4.进一步理解算法与数据结构的关系。
5.培养学生的信息意识和计算思维能力。
教学重点
1.掌握常用的数据查找方法、理解迭代和递归概念；
2.进一步理解算法与数据结构的关系。
教学难点
1.进一步理解算法与数据结构的关系；
2.培养学生的信息意识和计算思维能力。
教学方法
体验法、讲授法、讨论法、示例法
教学准备
计算机教室、多媒体设备、多媒体广播软件、Python编程环境、待查找的商品价格数据、教学课件等。
教学过程
一、新课导入
复习上节课的内容——顺序查找法。
1.核心概念
查找算法是程序中经常用到的算法。假定要从n个元素中查找 x 的值是否存在，最原始的方法是从头到尾挨个查找，这种查找的方法叫顺序查找方法。
2.顺序查找基本思路
在一组数据中，从第一个数据开始，按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。若某个数据与给定值相等，则查找成功，找到所查数据的位置;反之查找不成功。
3.顺序查找法流程图
二、二分查找法
1.核心概念
迭代法：用计算机解决问题的一种基本方法。是一种不断用变量的旧值递推出新值的过程，常用于重复性操作。
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构 ( https: / / baike. / item / %E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84 / 1347176" \t "https: / / baike. / item / %E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE / _blank )，而且表中元素按关键字有序排列。
2.查找过程
首先，假设表中元素是按升序排列，将表中间位置记录的关键字 ( https: / / baike. / item / %E5%85%B3%E9%94%AE%E5%AD%97" \t "https: / / baike. / item / %E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE / _blank )与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录 ( https: / / baike. / item / %E8%AE%B0%E5%BD%95 / 1837758" \t "https: / / baike. / item / %E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE / _blank )将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录 ( https: / / baike. / item / %E8%AE%B0%E5%BD%95 / 1837758" \t "https: / / baike. / item / %E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE / _blank )，使查找成功，或直到子表不存在为止，此时查找不成功。
3.算法要求
①必须采用顺序存储结构 ( https: / / baike. / item / %E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" \t "https: / / baike. / item / %E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE / _blank )。
②必须按关键字大小有序排列。
4.二分查找的实现与分析
二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。在以下介绍的实现方法中，有序数据集存放在sorted中，sorted是一块连续的存储空间。参数target是要查找的数据。
此实现过程的实施是通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。首先，将left和right分别设置为0和size-1。在循环的每次迭代过程中，将middle设置为left和right之间区域的中间值。如果处于middle的元素比目标值小，将左索引值移动到middle后的一个元素的位置上。即下一组要搜索的区域是当前数据集的上半区。如果处于middle的元素比目标元素大，将右索引值移动到middle前一个元素的位置上。即下一组要搜索的区域是当前数据集的下半区。随着搜索的不断进行，left从左向右移，right从右向左移。一旦在middle处找到目标，查找将停止；如果没有找到目标，left和right将重合。下图显示了此过程。
二分查找的时间复杂度取决于查找过程中分区数可能的最大值。对于一个有n个元素的数据集来说，最多可以进行lg n次分区。对于二分查找，这表示最终可能在最坏的情况下执行的检查的次数：例如，在没有找到目标时。
5.二分查找Python程序实现
def bin_search(data_list, val): low = 0 # 最小数下标 high = len(data_list) - 1 # 最大数下标 while low <= high: mid = (low + high) // 2 # 中间数下标 if data_list[mid] == val: # 如果中间数下标等于val, 返回 return mid elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标 high = mid - 1 else: # 如果val在中间数右边, 移动low下标 low = mid + 1 return # val不存在, 返回Noneret = bin_search(list(range(1, 10)), 3)print(ret)
三、体验使用二分查找法查找商品
假设该店铺出售的另一晶种商品有11种价格，按从小到大排序，价格为5、13、19,21、37、56、64、75、80、88、92。现要查找价格为21的商品在商品序列中的位置，可采用以下方法。
1.使用迭代法
首先确定待查价格所在区间，先将整个区间一分为二如图5-8所示。
图5-8 有序的商品价格序列
用low(序列的下界)指向第一个商品，high(上界)指向最后一个商品，mid(中间位置)指向中间价格对应的商品，待查价格为21，首先将21与mid指的中间位置的价格56比较，因21<56，则21必然在56之前的区间中，那么就在5、13、19、21、37中用同样的方法查找，如图5-9所示。
图5-9序列按价格折半取前半段
继续将21与前半段{5,13,19,21,37}的中间元素比较，因21>19,则在19的后半段{21,37}中查找，如图5-10所示。
图5-10 序列再折半
待查元素21与中间元素21比较相等，即找到了，查找结束，得到21在序列中的位置为4。
思考与讨论？
1.若序列是无序序列能用这种方法查找吗？为什么？
不能。因为前半段可能有比中间元素大的，后半段也可能有比中间元素小的。所以无法判断在怎样的范围继续查找。
2.中间位置如何求得？
下边界+上边界除以2向下取整，即int((low+high)/2)
3.二分查找只能在顺序存储结构即数组存储序列下实现，为什么？
因为二分查找使用的下边界和上边界是数组的下标，而链式存储结构则没有下标来表示元素间的先后逻辑关系。
4.送代还能运用在其他什么场合？
例如：验证角谷猜想：对于任意一个自然数n，若n为偶数，则将其除以2；若n为奇数，则将其来乘以3，然后再加1。如些经过有限次运算后，总可以得到自然数1。
2.使用递归法
二分查找中每次查找的区间是不同的，在不断缩小，但在找方法是一样的，所以也可以用递归(recursion)来实现。假设有这样一种函数BinSearch(r,low,high,k)，其中r代表存储数据元素的数组，low代表区间最左边的数据元素的数组下标，high代表区间最右边的数据元素的数组下标。k代表待查关键字。
图5-11存放商品序列的数组
针对图5-11所示价格有序商晶序列，可以使用BinSearch(r,1,11,21)调用上述丽数，因为21小于当前区间中点第6位置上的价格56,所以取前半段，即要去调用BinSearch(r,1,5,21)，因为21大于当前区间中点第3位置上的价格19,所以取后半段，即要去调用BinSearch(r.4.5.21)。此时中点第4位置上的价格等于待查商品价格21，查找完成，但函数执行并未完成，位于最上层的BinSearch(r,1,11,21并未获得结果。所以要一层一层返回21的位置(数组下标4,直至函数BinSearch(r,1,11,21)的值为4结束，如图5-12所示。
图5-12递归调用与返回
思考与讨论
1.若要查找80,BinSearch函数如何调用？
2.递归还能运用在其他什么场合？
例如，计算斐波那契(Fibonacci)数列的第几项函数fib(n)写成递归函数有：
def fib(n)：
if(n==0)：
return 0
else:
if(n==1)：
return1
else:
return fib(n-1)+fib(n-2)
四、课堂活动
1.在以下流程框图(局部)中完成二分在找算法(迭代法，low指示查找区间的下界，high指示查找区间的上界，待查元素k,n为元素个数，序列在数组r中)；编程实现，并运行测试(可参考配套资源中的“一分查找。py"程序)。
参考答案：
程序：
r=[5,13,19,21,37,56,64,75,80,88,92]
k=63 #k为查找值
low=0
high=10
while low<=high;
mid=int(low+high)/2
if k!=r[mid]：
if k>r[mid]：
low=mid+1
else:
high=mid-1
else:
break
if low>high:
print(-1)#若不存在，输出-1
else:
print(mid) #输出为待查找数据在列表中的下标
2.画出二分在找的递归算法流积图。(0指京在北区间的下界，high指示在找区间的上界，待查元素k,序列在数组(中)：完成程序，编程实现、并运行测试(可参考配套资源中的“二分查找递归。py”程序。
流程图：
程序：
def BinSearch(r,low,high,k):
if(low<=high)：
mid=
if(kreturn BinSearch( );
else:
if(k>r[mid].key)：
return BinSearch( );
else:
return mid
else:
return-9999
参考答案：
流程图：
程序：
def BinSearch(r,low,high,k):
if(low<=high)：
mid=int((low+high)/2)
if(kreturn BinSearch(r,low,mid-1,k);
else:
if(k>r[mid].key)：
return BinSearch(r,mid+1,high,k);
else:
return mid
else:
return-9999
r=[5,13,19,21,37,56,64,75,80,88,92]
k=64 #k为待查找数据
low=0
high=10
ans=binsearch(r,low,high,k)
print(ans)
#输出为待查找数据在列表中的下标
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
HYPERLINK "http://21世纪教育网(www.21cnjy.com)
" 21世纪教育网(www.21cnjy.com)(共45张PPT)
第二课时 体验使用二分查找法查找商品
信息技术沪教版 选择性必修1
第五单元 排序与查找
项目九 实现查找指定商品
——查找算法的应用及数据结构的选择
一、新课导入
二、二分查找法
三、体验使用二分查找法查找商品
四、课堂活动
一、新课导入
1.核心概念
查找算法是程序中经常用到的算法。假定要从n个元素中查找 x 的值是否存在，最原始的方法是从头到尾挨个查找，这种查找的方法叫顺序查找方法。
2.顺序查找基本思路
在一组数据中，从第一个数据开始，按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。若某个数据与给定值相等，则查找成功，找到所查数据的位置;反之查找不成功。
假定有n个记录存放在数组r[1]，r[2]，…，r[n]中，其中第i个记录的关键字值为r[i].key。待查关键字为k，将k依次与r[n].key，r[n-1].key，...，r[1].key 进行比较，一旦某个r[i]. key等于k，查找成功，返回下标i，若所有的数据元素都与k值不相等，则给出查找失败(i=0)的信息。
3.流程图
二、二分查找法
1.核心概念
迭代法：用计算机解决问题的一种基本方法。是一种不断用变量的旧值递推出新值的过程，常用于重复性操作。
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
2.查找过程
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
3.算法要求
②必须按关键字大小有序排列。
①必须采用顺序存储结构。
4.二分查找的实现与分析
二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。在以下介绍的实现方法中，有序数据集存放在sorted中，sorted是一块连续的存储空间。参数target是要查找的数据。
4.二分查找的实现与分析
此实现过程的实施是通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。首先，将left和right分别设置为0和size-1。在循环的每次迭代过程中，将middle设置为left和right之间区域的中间值。如果处于middle的元素比目标值小，将左索引值移动到middle后的一个元素的位置上。即下一组要搜索的区域是当前数据集的上半区。如果处于middle的元素比目标元素大，将右索引值移动到middle前一个元素的位置上。即下一组要搜索的区域是当前数据集的下半区。随着搜索的不断进行，left从左向右移，right从右向左移。一旦在middle处找到目标，查找将停止；如果没有找到目标，left和right将重合。
4.二分查找的实现与分析
5.二分查找Python程序实现
def bin_search(data_list, val):
low = 0 # 最小数下标
high = len(data_list) - 1 # 最大数下标
while low <= high:
mid = (low + high) // 2 # 中间数下标
if data_list[mid] == val: # 如果中间数下标等于val, 返回
return mid
elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标
high = mid - 1
else: # 如果val在中间数右边, 移动low下标
low = mid + 1
return # val不存在, 返回None
ret = bin_search(list(range(1, 10)), 3)
print(ret)
三、体验使用二分查找法查找商品
假设该店铺出售的另一晶种商品有11种价格，按从小到大排序，价格为5、13、19、21、37、56、64、75、80、88、92。现要查找价格为21的商品在商品序列中的位置，可采用以下方法。
1.使用迭代法
首先确定待查价格所在区间，先将整个区间一分为二如图5-8所示。
1.使用迭代法
用low(序列的下界)指向第一个商品，high(上界)指向最后一个商品，mid(中间位置)指向中间价格对应的商品，待查价格为21，首先将21与mid指的中间位置的价格56比较，因21<56,则21必然在56之前的区间中，那么就在5、13、19、21、37中用同样的方法查找，如图所示。
1.使用迭代法
继续将21与前半段{5,13,19,21,37}的中间元素比较，因21>19，则在19的后半段{21,37}中查找，如图所示。
待查元素21与中间元素21比较相等，即找到了，查找结束，得到21在序列中的位置为4。
思考与讨论
1.若序列是无序序列能用这种方法查找吗？为什么？
思考与讨论
1.若序列是无序序列能用这种方法查找吗？为什么？
不能。因为前半段可能有比中间元素大的，后半段也可能有比中间元素小的。所以无法判断在怎样的范围继续查找。
思考与讨论
2.中间位置如何求得？
思考与讨论
2.中间位置如何求得？
下边界+上边界除以2向下取整，即int((low+high)/2)
思考与讨论
3.二分查找只能在顺序存储结构即数组存储序列下实现，为什么？
思考与讨论
3.二分查找只能在顺序存储结构即数组存储序列下实现，为什么？
因为二分查找使用的下边界和上边界是数组的下标，而链式存储结构则没有下标来表示元素间的先后逻辑关系。
思考与讨论
4.送代还能运用在其他什么场合？
思考与讨论
4.送代还能运用在其他什么场合？
例如：验证角谷猜想：对于任意一个自然数n，若n为偶数，则将其除以2；若n为奇数，则将其来乘以3，然后再加1。如些经过有限次运算后，总可以得到自然数1。
2.使用递归法
二分查找中每次查找的区间是不同的，在不断缩小，但在找方法是一样的，所以也可以用递归(recursion)来实现。假设有这样一种函数BinSearch(r,low,high,k)，其中r代表存储数据元素的数组，low代表区间最左边的数据元素的数组下标，high代表区间最右边的数据元素的数组下标。k代表待查关键字。
2.使用递归法
针对图5-11所示价格有序商晶序列，可以使用BinSearch(r,1,11,21)调用上述丽数，因为21小于当前区间中点第6位置上的价格56,所以取前半段，即要去调用BinSearch(r,1,5,21)，因为21大于当前区间中点第3位置上的价格19,所以取后半段，即要去调用BinSearch(r.4.5.21)。此时中点第4位置上的价格等于待查商品价格21，查找完成，但函数执行并未完成，位于最上层的BinSearch(r,1,11,21并未获得结果。所以要一层一层返回21的位置(数组下标4,直至函数BinSearch(r,1,11,21)的值为4结束，如图5-12所示。
2.使用递归法
思考与讨论
1.若要查找80,BinSearch函数如何调用？
思考与讨论
1.若要查找80,BinSearch函数如何调用？
思考与讨论
2.递归还能运用在其他什么场合？
思考与讨论
例如，计算斐波那契(Fibonacci)数列的第几项函数fib(n)写成递归函数有：
def fib(n)：
if(n==0)：
return 0
else:
if(n==1)：
return1
else:
return fib(n-1)+fib(n-2)
四、课堂活动
1.在以下流程框图(局部)中完成二分在找算法(迭代法，low指示查找区间的下界，high指示查找区间的上界，待查元素k,n为元素个数，序列在数组r中)；编程实现，并运行测试(可参考配套资源中的“一分查找。py"程序)。
参考答案：
参考答案：
r=[5,13,19,21,37,56,64,75,80,88,92]
k=63 #k为查找值
low=0
high=10
while low<=high;
mid=int(low+high)/2
if k!=r[mid]：
if k>r[mid]：
low=mid+1
else:
high=mid-1
else:
break
if low>high:
print(-1)#若不存在，输出-1
else:
print(mid) #输出为待查找数据在列表中的下标
2.画出二分在找的递归算法流积图。(0指京在北区间的下界，high指示在找区间的上界，待查元素k,序列在数组(中)：完成程序，编程实现、并运行测试(可参考配套资源中的“二分查找递归。py”程序。
程序：
def BinSearch(r,low,high,k):
if(low<=high)：
mid=
if(kreturn BinSearch( );
else:
if(k>r[mid].key)：
return BinSearch( );
else:
return mid
else:
return-9999
参考答案：
程序：
def BinSearch(r,low,high,k):
if(low<=high)：
mid=int((low+high)/2)
if(kreturn BinSearch(r,low,mid-1,k);
else:
if(k>r[mid].key)：
return BinSearch(r,mid+1,high,k);
else:
return mid
else:
return-9999
参考答案：
参考答案：
r=[5,13,19,21,37,56,64,75,80,88,92]
k=64 #k为待查找数据
low=0
high=10
ans=binsearch(r,low,high,k)
print(ans)
#输出为待查找数据在列表中的下标
谢谢
21世纪教育网（www.21cnjy.com) 中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php
