16.基本查找算法 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

第十六章 数据查找 一、顺序查找 def Sequential_Search(a,key):     for i in range(len(a)):         if a[i] == key:             return i     return False d = [25,22,13,18,14,11,17,19] key = 18 if Sequential_Search(d,key):     print("查找成功") else:     print("未找到key值") 二、二分查找 1.二分查找基础代码 二分查找又称折半查找，对分查找。它是一种效率很高的查找方法，但被查找的数据序列必须是有序的。二分查找的示例代码如下 def Binary_Search(a,key):     L,R = 0,len(a)-1     while L <= R:         m = (L+R)//2   #左偏 m=(L+R+1)//2为右偏         if a[m] == key:             return m         if key < a[m]: #连续key问题，找第一个key则需改为key<=a[m]             R = m-1         else:             L = m+1     return False key = 15 d = [6,12,15,18,22,25,28,35,46,60] ans = Binary_Search(d,key) if ans:     print("查找成功!第"+str(ans+1)+"个") else:     print("没有找到!") 2.二分查找的特性 2.1二分查找基本思路：二分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素与查找键不同，根据数组元素的有序性，就可以确定在数组的前半部分还是后半部分继续查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。 2.2二分查找的时间复杂度：对于规模为n的数据进行对分查找，每次对分都可以将问题规模减半。在最坏情况下，直到第k轮才匹配到查找键，可得 k = log2n 。故二分查找的时间复杂度为O(log2n)。 3.二分查找常见的问题 3.1查找键key固定（也称“单key”问题）：直接将key带入代码运行即可 3.2查找键key不确定（也称“多key”问题）：根据代码每一轮产生的m值画对分查找树。示例代码中的数组绘制的对分查找树如下。 对分查找树有很多妙用，在做习题时需要慢慢积累。 3.3查找值key存在，且不止一个（又称“连续key”问题）：这种问题需要根据a[m]==key时，后续查找范围左移还是右移，确定最后返回的是最前还是最后key的位置。 4.对分查找的其他经典类型（注意加框处与基础版本的不同） def Binary_Search1(a,key):     L,R = 0,len(a)     while L < R:         m = (L+R)//2   #左偏         if a[m] == key:             return m         if key < a[m]:             R = m         else:             L = m+1     return False def Binary_Search2(a,key):     L,R = -1,len(a)-1     while L < R:         m = (L+R+1)//2   #右偏         if a[m] == key:             return m         if key < a[m]:             R = m-1         else:             L = m     return False 对分查找可以修改的地方很多，导致对分查找的代码十分灵活，查找的结束条件也不是固定的，做题时务必将实际例子带到代码中执行验证。 【补充】修改对分查找代码易产生的错误 def Binary_Search1(a,key):     L,R = 0,len(a) #(1)     while L < R:         m = (L+R)//2   #左偏         if a[m] == key:             return m         if key < a[m]:             R = m #(2)         else: