数据查找 【核心知识 精讲精研】 浙教版（2019）高中信息技术选修1

5.4数据查找顺序查找二分查找查找又称检索，计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。通常，程序将按照查找的结果（找到或未找到）来决定接着应执行后面哪一个计算步骤。你能在上图中找到那个特别的数字3吗？顺序查找算法思想顺序查找又称线性查找，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。①算法简单，对数据是否有序没有要求。②查找效率较低，当数据量大时不宜使用。算法特点顺序查找以“在成绩系统中查找某学号”为例，假定某学习小组8名学生的学号数据存储在数组d中，要查找的学生学号（查找键）已经存储在变量key中。01234567d2522131814111719key1801234567d2522131814111719key15找到未找到你能在上图中找到那个特别的数字3吗？顺序查找将待查找数据存储于数组d中要查询的数据存储于变量key中②依次将每个元素与key比较③若某个关键字等于键值则查找成功；

所有元素比较完毕仍找不到，则查找失败顺序查找将待查找数据存储于数组d中要查询的数据存储于变量key中②依次将每个元素与key比较③若某个关键字等于键值则查找成功；

所有元素比较完毕仍找不到，则查找失败#读取数据按行存储到数组d中#d=[“555555...”,“555555...”,...]flag=Falseforiinrange(len(d)):#遍历每一行forjinrange(__________):#遍历每一列if

:

print("3在第%d行,第%d列"%(i+1,j+1))flag=Truebreakif

:print("不存在特殊字符")d[i][j]==”3”flag==Falselen(d[i])枚举算法顺序查找小结1.顺序查找本质上是一种__________思想，顺序查找程序就是用循环来枚举所有要查找的对象，然后在循环体内用条件判断当前枚举出的对象是否等于查找对象。2.一般情况是，当需要查找的数据规模为n时，顺序查找最少查找____次，最多查找_____次，其平均查找次数是________。3.顺序查找最大的优点是查找的数据可以是乱序的，但是其缺点是查找效率太低。顺序查找将待查找的数值与序列中的数逐个进行比较，直到找出与给定数值相同的数为止，其时间复杂度为_____。枚举算法1n(1+n)/2O(n)二分查找算法思想二分查找又称折半查找，对分查找。它是一种效率很高的查找算法，但被查找的数据序列必须是有序的。首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，则根据有序性，确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内，继续按上述方法，直到获得最终结果。算法特点①要求被查找数据必须有序。②查找效率高，适用于大数据查找。612151822252835465860612151822252835465860612151822252835465860612151822252835465860612151822252835465860二分查找ijmidKey=12开始：

第1遍查找：

第2遍查找：

第3遍查找：

第4遍查找：

ij012345678910ijmidijmidijmid二分查找算法演算（1）key与d[mid]的大小比较影响下一次查找的范围[i,j]。①若d[mid]<key，则查找后半段：i=________，j=______②若d[mid]>key，则查找前半段：i=________，j=______（2）继续重复进行查找的条件。当i<=j时（3）对分查找最多的查找次数(n个数据)。最多次数=int(log2n)+1∵n个数据对分x次最后变为1个数据∴n/2**x=1∴x=log2n∵最后一个数据还要参与一次查找∴最多次数=int(log2n)+1mid+1jimid-1二分查找①存储待查找数据key等key=12;f=Falsed=[6,12,15,18,22,25,28,35,46,58,60]②i和j定义子数组的边界i=0;j=len(d)-1当存在待查找的子数组时，继续查找③确定本次查找的数据下标

本次查找的数据下标为i,j的中点④若找到则停止循环，记录位置

判断中点数据是否为key值：

找到记录下标;做找到标记 break

没找到时，若中点数据偏大： key应在中点左侧

没找到时，若中点数据偏小： key应在中点右侧⑤调整子数组范围继续查找iff==True:print("查找成功！第"+str(b+1)+"个数据")else:print("没有找到！")⑥输出查找结果二分查找key=12;f=Falsed=[6,12,15,18,22,25,28,35,46,58,60]i=0;j=len(d)-1当存在待查找的子数组时，继续查找

本次查找的数据下标为i,j的中点

判断中点数据是否为key值：

找到记录下标;做找到标记 break

没找到时，若中点数据偏大： key应在中点左侧

没找到时，若中点数据偏小： key应在中点右侧iff==True:print("查找成功！第"+str(b+1)+"个数据")else:print("没有找到！")key=12;f=Falsed=[6,12,15,18,22,25,28,35,46,58,60]i=0;j=len(d)-1while

:m=(i+j)//2ifd[m]==key:f=True;b=mbreakif

:j=m-1else:_________iff==True:print("查找成功！第"+str(b+1)+"个数据")else:print("没有找到！")i<=jkey<d[m]i=m+1二分查找defbsearch(s,array):if____________:print("未找到")returnFalsemid=(len(array)-1)//2if

:print("找到了")returnTrueelifs<array[mid]:returnbsearch(s,array[:mid])else:return__________________key=12d=[6,12,15,18,22,25,28,35,46,58,60]print(bsearch(key,d))len(array)==0array[mid]==sbsearch(s,array[mid+1:])二分查找过程中的每一次判断都是将需要查找的值和数组的中间值进行不断的比较，直到找到或找遍整个序列。因此，二分查找算法可利用递归来实现。查找算法小结查找算法顺序查找二分查找优点①算法简单，对数据是否有序没有要求。②查找效率高，适用于大数据查找。缺点②查找效率较低，当数据量大时不宜使用。①要求被查找数据必须有序。查找次数一般情况是，当需要查找的数据规模为n时，顺序查找最少查找____次，最多查找____次，其平均查找次数是________。无论是否找到，最多进行_____________次查找。算法思想顺序查找本质上是一种_______算法思想。二分查找思想符合_______算法的思想。时间复杂度1n(1+n)/2int(log2n)+1枚举递归O(n)O(log2n)二叉排序树从根结点到待查结点的一条路径为25→15→6→12，比较次数为4次。通过观察可知，在n个元素排序的顺序表里，某一次查找过程中，所做比较次数不超过判定树的高度加1，即int(log2n)+1二叉排序树二叉排序树：①若左子树不为空，则左子树的值均小于它的根节点的值②若右子树不为空，则右子树的值均大于它的根节点的值③它的左右子树也分别为二叉排序树记录关键字排列的有序表：[1,16,24,35,47,59,62,73,88,99]。采用二分查找，画出判定树，并给出查找关键字24的记录过程。写出该判定树的后序遍历结果。47-16-24课堂练习47167312488995962351-35-24-16-62-59-99-88-73-47（）1.某Python程序如下，当输入不同的key值，运行该程序段后，n的值可能有A.5种 B.6种 C.7种 .8种a=[86,75,58,46,20,18,12,5]key=int(input())n=0;i=0;j=len(a)-1whilei<=j:m=(i+j)//2ifkey>a[m]:j=m-1;n=n-1else:i=m+1;n=n+1A课堂练习1、某数组有10个元素，依次为5，12，16，23，27，30，35，41，49，50，下列选项中正确的是（

）A、使用对分查找査找数据12，需要的查找次数是3次B、使用顺序查找査找数据60，需要的查找次数是10次C、使用对分查找查找数据41，需要的查找次数是2次D、使用顺序查找查找数据5，需要的查找次数是0次C课堂练习2.有如下自定义函数调用语句print(fun([5,4,7,1,4,3,7,9],4))后,程序输出的结果为() deffun(a,key): n=len(a) i=0 whilei<n: ifa[i]==key: break i+=1 ifi==n: i=-1 returni A.-1 B.1 C.2 D.4B3.有如下Python程序段：key=int(input(“key=”))s=0a=[]foriinrange(10):a.append(i+1)foriinrange(len(a)):ifa[i]%key==0:s=s+1print(s)当输入的key=5时，程序运行结束后，输出的值为（

）A.0B.1C.2D.3C4.某二分查找算法的程序如下：i＝0j＝7n＝0whilei<＝j：n＝n＋1m＝(i＋j)//2ifkey＝＝d[m]：breakelifkey>d[m]：j＝m－1else：i＝m＋1数组元素d[0]到d[7]的值依次为″83，75，62，41，33，27，16，2″，若运行该程序段后，n的值为2，则key的值可能是(

)A.62或16

B.62或27C.75或27 D.75或16C5.有如下python程序段：a=[2,6,8,8,2,4,7,3]p=0foriinrange(1,len(a)):ifa[i]>a[p]:p=i则运行该段代码后，变量p的值为（

）A.0B.2C.3D.8B6、某对分查找算法的Python程序段如下：a=[8,17,24,30,36,40,55,58,61,66]L,R=0,9；s=[]key=int(input("请输入要查找的数据："))whileL<=R:m=(L+R+1)//2ifa[m]==key: breakelifa[m]>key: R=m-1else: L=m+1s.append(a[m])print(s)执行该程序段，当输入的值为30时，程序输出的结果是（

）A、[40,24]B、[40,24,36]C、[24,36]D、[36,17,24]B7、有如下Python程序段：li=[12,18,43,5,3,21,43,75,23,54,13,45]key=int(input("输入要查找