专题18 查找算法 知识点一 二分查找的算法思想 1.有如Python程序段： import random def find(x，y)： m＝(x＋y＋1)//2 if a[m]＝＝key： return m if a[m]>key： y＝m－1 else： x＝m＋1 return find (x，y) a＝[2，4，6，8，10，12，14，16] key＝random.choice(a) #从序列的元素中随机挑选一个元素 i＝0；j＝len(a)－ 1 xb＝find(i，j) print(xb，key) 上述程序执行完后，函数find被调用的最多次数是( ) A.3 B.4 C.5 D.6 2.某对分查找算法的Python程序如下： f＝[0]*20 i＝0；j＝19；n＝0；m＝0 while i<＝j and f[m]＝＝0： m＝(i＋j＋1)//2 n＝n＋1 if a[m]＝＝key： f[m]＝1 elif a[m]
key： j＝m－1；n＝n－1 else： i＝m＋1；n＝n＋1 执行该程序段后，下列说法正确的是( ) A.该程序若要实现对分查找，要求数组a按降序排列 B.若n为－2，则查找key值可能等于a[3]的值 C.若n为2，则查找 key 的值可能小于a[10] D.n的值最小为－4，最大为4 5.有如下Python程序： a＝[83，80，66，46，44，36，21，16，15，12] key＝int(input(″输入要查找的数：″)) i＝0；j＝9 ans＝″″ while i<＝j： m＝(i＋j＋1)//2 if key＝＝a[m]： break elif key>a[m]： j＝m－1 else： i＝m＋1 ans＝ans＋str(a[m])＋″ ″ print(ans) 执行该程序，输入 80，则输出的结果是( ) A.36 66 B.44 80 C.36 46 D.44 66 6.某二分查找算法的Python程序段如下： i，j＝0，24 n＝0 while i<＝j： m＝(i＋j＋1)//2 n＝n＋1 if key＝＝a[m]： break if key>a[m]： i＝m＋1 else： j＝m－1 print(n) 列表a中各元素值依次为1～25，若查找键key为下列选项的值，程序段执行后，输出结果与其他三项不同的是( ) A.7 B.12 C.19 D.22 7.如下Python程序段： import random a＝[1，3，5，7，9，11，13，15] key＝random.randint(1，8)*2 i，j＝0，len(a)－1 s＝0 while i<＝j： m＝(i＋j＋1)//2 if a[m]＝＝key： break if a[m]>key： j＝m－1；s－＝1 else： i＝m＋1；s＋＝1 print(s) 上述程序执行完以后，s 的值可能有( ) A.4种 B.5种 C.7种 D.8种 8.小明为英文字母A～Z定义了一套全新的二进制编码规则，代码如下 s＝[chr(i＋65)for i in range(26)] dc＝{} for k in s： i＝0 j＝len(s)－1 rt＝″0″ while i<＝j： m＝(i＋j)//2 if s[m]＝＝k： dc[k]＝rt break elif s[m]j： return 0 m＝(i＋j)//2 if key＝＝a[m]： return m if key
