资源简介

(共23张PPT)
六、 查找算法及程序实现
第五章　数据结构与算法
知识过关
数据查找的概念
查找(Search)又称检索,计算机根据所给条件查找出满足条件的对象,即在存储的一批数据内寻找出一个特定的数据,或者确定在该批数据内是否存在这样的数据。若没有找到满足条件的对象,则返回特定值,表明查找失败;若查找到满足条件的对象,则表明查找成功,一般要求返回该对象的存储位置或对象值本身。查找的方法主要有顺序查找和二分查找,重难点是二分查找算法。
(1)顺序查找。
①顺序查找的概念。
从第一个数据开始,按数据的顺序逐个将数据与给定的值进行比较。若某个数据与给定值相等,则查找成功,找到所查数据的位置;反之,则查找不成功。顺序查找算法简单,对数据表中的元素是否有序没有要求。
顺序查找的过程:在列表a=[3,9,1,5,8,0,6,7,2,4]中查找关键字key为5的元素。可知顺序查找的过程如下:从头开始查找,找到key=5的数据,共查找4次,如果从尾部开始顺序查找,那么一共需要查找7次。
②顺序查找的效率。
使用顺序查找时,最理想的情况是比较一次就能够找到目标数据,最差的情况是需要比较完所有的数据后才能确定是否找到目标数据。因此,此种查找方法查找效率低,当数据量较大时不宜采用。
一般情况下,当需要查找的数据规模为n时,顺序查找最少查找1次,最多查找n次,其平均查找次数是(1+n)/2。
顺序查找最大的优点是查找的数据可以是乱序的,但是其缺点是查找效率太低。顺序查找将待查找的数值与序列中的数逐个进行比较,直到找出与给定数值相同的数为止,其时间复杂度为O(n)。
顺序查找算法的Python程序如下:
d=[3,9,2,5,8,0,6,7,6,4]　　# 列表d数据可以是乱序
key=5　　　　　# key为查找关键词
flag=False
for i in range(len(d)):
　　if d[i] == key:
　　　　flag=True
　　　　break
if flag==True:
　　print("查找成功!")
else:
　　print("未找到")
(2)二分查找。
①二分查找的概念。
二分查找(又称对分查找)算法先把待查找的数据进行排序,即二分查找的前提条件是数据必须有序,然后按照折半思想进行查找。假设待查找数据按升序排列,将数组中间位置元素与查找关键字key比较,若相等,则查找成功;否则利用中间位置将数组分成前、后两部分,若查找关键字key大于中间位置元素,则进一步查找后半部分,否则进一步查找前半部分。重复以上过程,直到找到key(此时查找成功),或数据不存在为止(此时查找不成功)。
二分查找算法的核心代码(已知列表d的数据已经进行升序排列)如下:
key = int(input())
flag = False
i = 0;j = len(d)－1
while i <= j and not flag:
　　m = (i + j)//2
　　if key == d[m]:
　　　　flag = True
　　　　k = m
　　　　break　
　　elif key < d[m]:
　　　　j = m－1
　　else:
　　　　i = m +1
if flag==True:
　　print("查找成功!第",str(k),"个")
else:
　　print("未找到!")
②二分查找的效率。
二分查找的缺点是要求查找数据必须有序,当查找数据量大时,二分查找的查找效率较高,无论是否找到,最多进行int(log2n)+1次查找,其中n为数据规模。二分查找的思想符合递归算法的思想。二分查找的优点是,当数据规模较大时,其效率较高,其时间复杂度是O(log2n)。
典例精选
【例1】 (2024·浙江6月选考)某二分查找算法的Python程序段如下:
i,j = 0,len(d)－1
while i <= j:
　　m = (i+j)//2　#语句①
　　if key == d[m]:
　　　　break
　　elif key < d[m]:
　　　　j = m－1
　　else:
　　　　i = m+1
当d为[6,12,15,18,22,25,28,35,46]时,运行该程序段查找key,语句①的执行次数小于
等于2;若将d修改为[6,12,15,18,22,25,28,35,46,58],重新运行该程序段,查找同一key
值,则语句①的执行次数不. 可. 能. 为(　　)
A. 1　　 B. 2　　
C. 3　　 D. 4
【解析】 本题考查二分查找算法知识。根据题意可知,当数组d为[6,12,15,18,22,25,28,35,46]时,i=0,j=8,运行该程序段,语句①的执行次数小于等于2,因此查找的数key可能是这三个数:22(查找一次),12和28则各查找2次。若将d修改为[6,12,15,18,22,25,28,35,46,58],此时,i=0,j=9,由于中点位置m居中偏左,因此第一次查找的m=4,仍然是22,若往左查找,第二次依然是12。但若第二次往右查找,则找到的是35,而不是原先的28,然后继续第三次查找找到25,接着进行第四次查找,找到28,此时查找过程结束。综上所述,C符合题意。
C
【例2】 (2024·浙江1月选考)某算法的部分流程图如图所示,若n的值为7,key的值为78,数组元素a[0]至a[n－1]依次存放7,12,24,36,55,
78,83,执行这部分流程后,输出c的值为(　　)
A. 0 B. 1
C. 2 D. 3
【解析】 本题考查流程图及二分查找算法知识。由流程图可知,该算法属于二分查找,且查找中若查找到key值,将退出查找过程。第一次查找, I=0,j=6,key=78,m=3,由于a[3]=36B
【例3】 某二分查找算法的Python程序段如下:
a=[21,22,23,24,25,26,27,28,29,30]
key=int(input("key="))
c=0
i, j=0,9
m=(i+j)//2
while i<=j and key!=a[m]:
　　if a[m]　　　　i=m+1
　　else:
　　　　j=m－1
　　m=(i+j)//2
　　c+=1
　　print(c)
若程序运行后,输出结果是3,则key的值可能是(　　)
A. 21或23　　　 B. 24或27
C. 26或29 D. 23或30
【解析】 本题考查二分查找算法知识。根据程序代码可知,退出循环的条件是i>j或者key=a[m]。根据本题算法绘制的二叉树如下图所示。从程序中可知,第1次计算m,c=0;第2次计算m,c=1;第3次计算m,c=2;第4次计算m,c=3。输出结果c的值为3,所以计算了4次m的值,key的值应为24、27、30中的一个。B正确。
B
【例4】 某二分查找算法的Python程序段如下:
import random
i = 0;j = 6;s = ""
key = random.randint(0,99)
while i <= j:
　　m = (i + j)// 2
　　if key == a[m]:
　　　　s = s + "M"; break
　　elif key < a[m]:
　　　　j = m － 1; s = s + "L"
　　else:
　　　　i = m + 1; s = s + "R"
print(s)
列表a=[24,35,38,41,45,69,78]。该程序段执行后,s中显示的内容可能是(　　)
A. RL　 B. LMR
C. RLR D. LRLM
【解析】 本题考查二分查找算法知识。由于查找的数key是一个随机数,本题可以使用排除法。根据常识可知,二分查找7个数最多查找3次(int(log2n+1)=3),D错误。而且找到后就会退出,所以“M”不可能在中间,B错误。如果只找了2次,必然是在找到的情况下才会发生,A错误。
C
自我检测
1. 列表a存储了10个数据。下列关于查找关键词key的说法,正确的是(　　)
A. 若列表a中数据无序,则只能使用二分查找key值
B. 若列表a中数据是有序的,则不可以使用顺序查找算法
C. 若可以使用二分查找,最多查找的次数是4次
D. 若可以使用顺序查找,最多查找的次数是9次
【解析】 本题考查查找算法。若列表a中数据无序,只能使用顺序查找,若有序则顺序查找和二分查找都可以。10个数据,使用二分查找最多查找次数为:int(log210)+1=4次,而顺序查找最多查找10次。C正确。
C
2. 有如下Python程序段:
a = [99,85,74,68,53,42,34,27,20,13]
key = int(input("请输入一个整数:"))
i,j,k,c,flag = 0,9,0,"N",False
while i <= j and flag == False:
　　m = (i + j + 1)//2
　　k = k + 1
　　if key == a[m]:
　　　　c = "Y"
　　　　flag = True
　　if key > a[m]:
　　　　j = m －1
　　else:
　　　　i = m + 1
print(c,k)
执行该程序段后,下列说法中,正确的是(　　)
A. 该程序段既能用于升序序列的查找,也能用于降序序列的查找
B. 若输出k的值为2,则c的值一定为Y
C. 若输入key的值为74,程序执行后变量i和j的值分别为0和4
D. 输入任意的两位正整数,k的值介于1和3之间
B
【解析】 本题考查二分查找算法。由程序中的if语句可知,若key大于a[m],j=m－1,否则i=m+1,所以该程序段只能用于降序序列的查找,A错误。当k=2时,i<=j肯定成立,所以程序是因为条件flag==False不成立才结束的,由此可知,经过2次查找找到了需要查找的整数,所以c的值一定为Y,B正确。查找74的过程如下表所示,程序执行后变量 i 和 j 的值分别为3和4,C错误。
i j m k a[m] c flag
0 9 0 N False
第1次循环 4 5 1 42 N False
第2次循环 3 2 2 74 Y True
当查找一个首尾数据时,k的值最大,应为4,D错误。
3. 某二分查找算法的Python程序段如下:
c=0
while i<=j:
　　m=(i+j)//2
　　c=c+1
　　if key>a[m] :
　　　　i=m+1
　　else:
　　　　j=m－1
print(c)
已知数组a的长度为8,为至少包含一个元素“4”的非降序序列,key为4。当加框处语句为“key>a[m]”时,c为3;当加框处语句改为“key>=a[m]”后,c为4。数组a中元素
“4”的索引范围不. 可. 能. 为(　　)
A. 2~5 B. 2~6
C. 5~6 D. 5~7
【解析】 当数组a中的元素“4”的索引为2~5时,两种方式的查找,c的值均为3。若要找到key后继续向后找能查找4次,最后一个元素“4”的索引必须大于等于6。A正确。
A

展开更多......

收起↑