5.4.2二分查找课件-浙教版高中信息技术选修1

5.4.2二分查找猜数游戏假设在1-100以内寻找某一个整数，如果我们每次都通过中间值来进行查找某一个数，那么我们几次以内能找到这个数？24502513192223247次找到！如果要找的数是其它数呢？二分查找又称折半查找，对分查找。它是一种效率很高的查找方法，但被查找的数据序列必须是有序的。二分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素的数值与查找键不同，根据数组元素的有序性，就可确定在数组的前半部分还是后半部分继续查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。在数组中的数据是有序的，若是升序的，是指下标越小的数组元素中存储的数据也越小，降序则相反。为简单起见，设数组d中存储了n个互不相同的数据，并且数组d中的数据是升序的，则应有：d[0]<d[1]<…<d[n-2]<d[n-1]。使用两个变量i和j分别记录查找范围内的第一个数组元素和最后一个数组元素的下标。开始时，整个数组中的所有n个元素都在查找范围内，即变量i的初值为0，j的初值为n-1，用(i,j)表示查找范围从d[i]起到d[j]为止。二分查找的基本方法是：在查找范围（i,j）内，可以利用数据的有序性，而不必逐个地进行查找。

（a）key<d[m]，查找键小于中点d[m]处的数据。因为数组d中的数据递增，可以确定在（m,j）内不可能存在值为key的数据，所以只需在新的范围（i,m-1）中继续查找。（b）key=d[m]，找到了需要的数据。（c）key>d[m]，由与（a）相同的理由，只需在新的范围（m+1,j）中继续查找。在通过一次比较后，新的查找范围不会超过上一次查找范围的一半。以规模为11的数组d为例，观察二分查找的过程。在数组d的11个元素中，已按增序存储了11个数据，要寻找的数据为12（已存储在变量key中）。查找过程中，查找范围的变化情况如下图所示：612151822252835465860012345678910Key=12开始：ij第一次比较：612151822252835465860012345678910ijm第二次比较：612151822252835465860012345678910ijm第三次比较：612151822252835465860012345678910ijm第四次比较：612151822252835465860012345678910ijm查找成功！规模为n的数组中进行二分查找的流程图。开始i0,jn-1i≤j?是计算中点m[(i+j)/2]d[m]=key?找到，输出信息是否否未找到，输出信息结束key<d[m]?jm-1im+1是否实现此算法的Python程序：key=12d=[6,12,15,18,22,25,28,35,46,58,60]f=False#i和j定义子数组的边界，一开始搜索的是整个数组i=0j=len(d)-1whilei<=j:m=(i+j)//2ifd[m]==key:f=Trueb=mbreakifkey<d[m]:#到左边去找j=m-1else:#到右边去找i=m+1iff==True:print(“查找成功！第”+str(b)+”个”)else:print(“没有找到！”)另一种写法：d=[6,12,15,18,22,25,28,35,46,58,60]i=0j=len(d)-1key=int(input(‘请输入查找值：’))whilei<=j:m=(i+j)//2ifd[m]==key:print(“找到了，索引位置为：”,m)breakifkey<d[m]:#到左边去找j=m-1else:#到右边去找i=m+1ifi>j:print(“没有找到！”)二分查找过程中，在每次关键字比较时，如果不匹配，那么根据匹配结果将查找表一分为二，排除没有包含查找键的那一半，然后在可能含有查找键的那一半中继续二分查找，直至找到查找键或找遍整个数组。处理思想是将一个大范围的查找问题转化为一个与原问题相似的查找范围较小的查找问题，并且查找能在一定条件下停止。这个思想符合递归算法的思想。二分查找算法的递归实现defbsearch(s,array):iflen(array)==0:print(“未找到！”)returnFalsemid=(len(array)-1)//2ifarray[mid]==s:print(“找到了!”)returnTrueelifs<array[mid]:returnbsearch(s,array[:mid])else:returnbsearch(s,array[mid+1:])key=12d=[6,12,15,18,22,25,28,35,46,58,60]print(bsearch(key,d))若查找对象采用链表结构，能否适用二分查找？一般而言，链表结构不适合采用二分查找，但这又并非绝对，链表结构可以通过数组来实现，从而二分查找也适用。二分查找过程可用一棵二叉树来描述，树中的每个根节点对应当前查找区间的中点元素，它的左子树和右子树分别对应该区间的左子表和右子表，如下图所示：251561218224628355860二分查找的判定树实例查找key为12的元素比较次数为4次

由于二分查找在有序表上进行，所以其对应的判定树就是一棵二叉排序树。二叉排序树也称为二叉查找树，这种结构的二叉树既能实现排序功能，也能实现查找功能。一、排序二叉排序树的排序功能主要通过二叉树的建立和遍历过程来实现，其在建立过程中要始终满足如下性质：1.若它的左子树不为空，则左子树上的所有节点的值均小于它的根节点的值。2.若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。3.它的左右子树也分别为二叉排序树。一组数据“23,20,13,18,14,11”建立的二叉排序树如下图所示，对此二叉树进行中序遍历时，结果为从小到大的有序序列：23201311181411,13,14,18,20,23二、查找二叉查找树的查找过程为：首先将给定值和根节点的关键字比较，若相等，则查找成功；若不相等，则根据给定值和根节点关键字之间的大小关系，在左子树或右子树中继续进行查找。若查到为空树时，说明该树中没有待查记录，故查找不成功。232013111814查找关键字key为14的节点小小大小路径：2320131814

练一练：1.在有序数组[12,23,34,45,46,5