沪教版（2019）2.体验使用二分查找法查找商品精品ppt课件

这是一份沪教版（2019）2.体验使用二分查找法查找商品精品ppt课件，文件包含项目九第二课时pptx、项目九第二课时doc等2份课件配套教学资源，其中PPT共44页， 欢迎下载使用。

三、体验使用二分查找法查找商品
查找算法是程序中经常用到的算法。假定要从n个元素中查找 x 的值是否存在，最原始的方法是从头到尾挨个查找，这种查找的方法叫顺序查找方法。
在一组数据中，从第一个数据开始，按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。若某个数据与给定值相等，则查找成功，找到所查数据的位置;反之查找不成功。 假定有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)的信息。
迭代法：用计算机解决问题的一种基本方法。是一种不断用变量的旧值递推出新值的过程，常用于重复性操作。 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
②必须按关键字大小有序排列。
①必须采用顺序存储结构。
4.二分查找的实现与分析
二分查找法实质上是不断地将有序数据集进行对半分割，并检查每个分区的中间元素。在以下介绍的实现方法中，有序数据集存放在srted中，srted是一块连续的存储空间。参数target是要查找的数据。
此实现过程的实施是通过变量left和right控制一个循环来查找元素（其中left和right是正在查找的数据集的两个边界值）。首先，将left和right分别设置为0和size-1。在循环的每次迭代过程中，将middle设置为left和right之间区域的中间值。如果处于middle的元素比目标值小，将左索引值移动到middle后的一个元素的位置上。即下一组要搜索的区域是当前数据集的上半区。如果处于middle的元素比目标元素大，将右索引值移动到middle前一个元素的位置上。即下一组要搜索的区域是当前数据集的下半区。随着搜索的不断进行，left从左向右移，right从右向左移。一旦在middle处找到目标，查找将停止；如果没有找到目标，left和right将重合。
5.二分查找Pythn程序实现
def bin_search(data_list, val): lw = 0 # 最小数下标 high = len(data_list) - 1 # 最大数下标 while lw <= high: mid = (lw + high) // 2 # 中间数下标 if data_list[mid] == val: # 如果中间数下标等于val, 返回 return mid elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标 high = mid - 1 else: # 如果val在中间数右边, 移动lw下标 lw = mid + 1 return # val不存在, 返回Nneret = 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.使用迭代法 用lw(序列的下界)指向第一个商品，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.若序列是无序序列能用这种方法查找吗？为什么？
不能。因为前半段可能有比中间元素大的，后半段也可能有比中间元素小的。所以无法判断在怎样的范围继续查找。
2.中间位置如何求得？
下边界+上边界除以2向下取整，即int((lw+high)/2)
3.二分查找只能在顺序存储结构即数组存储序列下实现，为什么？
因为二分查找使用的下边界和上边界是数组的下标，而链式存储结构则没有下标来表示元素间的先后逻辑关系。
4.送代还能运用在其他什么场合？
例如：验证角谷猜想：对于任意一个自然数n，若n为偶数，则将其除以2；若n为奇数，则将其来乘以3，然后再加1。如些经过有限次运算后，总可以得到自然数1。
2.使用递归法 二分查找中每次查找的区间是不同的，在不断缩小，但在找方法是一样的，所以也可以用递归(recursin)来实现。假设有这样一种函数BinSearch(r,lw,high,k)，其中r代表存储数据元素的数组，lw代表区间最左边的数据元素的数组下标，high代表区间最右边的数据元素的数组下标。k代表待查关键字。
2.使用递归法 针对图5-11所示价格有序商晶序列，可以使用BinSearch(r,1,11,21)调用上述丽数，因为21小于当前区间中点第6位置上的价格56,所以取前半段，即要去调用BinSearch(r,1,5,21)，因为21大于当前区间中点第3位置上的价格19,所以取后半段，即要去调用BinSearch()。此时中点第4位置上的价格等于待查商品价格21，查找完成，但函数执行并未完成，位于最上层的BinSearch(r,1,11,21并未获得结果。所以要一层一层返回21的位置(数组下标4,直至函数BinSearch(r,1,11,21)的值为4结束，如图5-12所示。
2.使用递归法
1.若要查找80,BinSearch函数如何调用？
2.递归还能运用在其他什么场合？
例如，计算斐波那契(Fibnacci)数列的第几项函数fib(n)写成递归函数有：def fib(n)： if(n==0)： return 0 else: if(n==1)： return1 else: return fib(n-1)+fib(n-2)
1.在以下流程框图(局部)中完成二分在找算法(迭代法，lw指示查找区间的下界，high指示查找区间的上界，待查元素k,n为元素个数，序列在数组r中)；编程实现，并运行测试(可参考配套资源中的“一分查找。py"程序)。
r=[5,13,19,21,37,56,64,75,80,88,92]k=63 #k为查找值lw=0high=10while lw<=high; mid=int(lw+high)/2 if k!=r[mid]： if k>r[mid]： lw=mid+1 else: high=mid-1 else: breakif lw>high: print(-1)#若不存在，输出-1else: print(mid) #输出为待查找数据在列表中的下标
2.画出二分在找的递归算法流积图。(0指京在北区间的下界，high指示在找区间的上界，待查元素k,序列在数组(中)：完成程序，编程实现、并运行测试(可参考配套资源中的“二分查找递归。py”程序。
程序：def BinSearch(r,lw,high,k): if(lw<=high)： mid= if(kr[mid].key)： return BinSearch( ); else: return midelse: return-9999
程序：def BinSearch(r,lw,high,k): if(lw<=high)： mid=int((lw+high)/2) if(kr[mid].key)： return BinSearch(r,mid+1,high,k); else: return midelse: return-9999
r=[5,13,19,21,37,56,64,75,80,88,92]k=64 #k为待查找数据lw=0high=10ans=binsearch(r,lw,high,k)print(ans)#输出为待查找数据在列表中的下标