查找算法是用来检索序列数据（群体）中是否存在给定的数据（关键字），常用查找算法有：
因树表查找、哈希查找的所需篇幅较多，就不在python教程分享详解Python查找算法的实现(线性、二分、分块、插值)讲解。python教程分享详解Python查找算法的实现(线性、二分、分块、插值)将详细介绍除树表、哈希之外的查找算法，并分析每一种算法的优点和缺点，并提出相应的优化方案。
线性查找也称为顺序查找，线性查找属于原始、穷举、暴力查找算法。容易理解、编码实现也简单。但是在数据量较多时，因其算法思想是朴素、穷举的，算法中没有太多优化设计，性能会很低下。
线性查找思想：
根据线性查找算法的描述，很容易编码实现：
''' 线性查找算法 参数： nums: 序列 key:关键字 返回值： 关键字在序列中的位置 如果没有，则返回 -1 ''' def line_find(nums, key): for i in range(len(nums)): if nums[i] == key: return i return -1 ''' 测试线性算法 ''' if __name__ == "__main__": nums = [4, 1, 8, 10, 3, 5] key = int(input("请输入要查找的关键字：")) pos = line_find(nums, key) print("关键字 {0} 在数列的第 {1} 位置".format(key, pos)) ''' 输出结果： 请输入要查找的关键字：3 关键字 3 在数列的 4 位置 '''
线性查找算法的平均时间复杂度分析。
1.运气最好的情况：如果要查找的关键字恰好在数列的第 1 个位置，则只需要查找 1 次就可以了。
如在数列=[4,1,8,10,3,5]中查找关键字 4 。
只需要查找 1 次。
2.运气最不好的情况：一至扫描到数列最尾部时，才找到关键字。
如在数列=[4,1,8,10,3,5]中查找是否存在关键字 5 。
则需要查找的次数等于数列的长度，此处即为 6 次。
3.运气不好不坏：如果要查找的关键字在数列的中间某个位置，则查找的概率是 1/n 。
n 为数列长度。
线性查找的平均查找次数应该=(1+n)/2。换成大 o 表示法则为 o(n) 。
大 o 表示法中忽视常量。
线性查找最糟糕情况是：扫描完整个数列后，没有所要查找的关键字。
如在数列=[4,1,8,10,3,5]中查找是否存在关键字 12 。
扫描了 6 次后，铩羽而归！！
改良线性查找算法
可以对线性查找算法进行相应的优化。如设置“前哨站”。所谓“前哨站”，就是把要查找的关键字在查找之前插入到数列的尾部。
def line_find_(nums, key): i = 0 while nums[i] != key: i += 1 return -1 if i == len(nums)-1 else i ''' 测试线性算法 ''' if __name__ == "__main__": nums = [4, 1, 8, 10, 3, 5] key = int(input("请输入要查找的关键字：")) # 查找之前，先把关键字存储到列到的尾部 nums.append(key) pos = line_find_(nums, key) print("关键字 {0} 在数列的第 {1} 位置".format(key, pos))
用"前哨站"优化后的线性查找算法的时间复杂度没有变化，o(n)。或者说从 2 者代码上看，也没有太多变化。
但从代码的实际运行角度而言，第 2 种方案减少了 if 指令的次数，同样减少了编译后的指令，也就减少了 cpu执行指令的次数，这种优化属于微优化，不是算法本质上的优化。
使用计算机编程语言所编写的代码为伪指令代码。
经过编译后的指令代码叫 cpu 指令集。
有一种优化方案就是减少编译后的指令集。
二分查找属于有序查找，所谓有序查找，指被查找的数列必须是有序的。如在数列=[4,1,8,10,3,5,12]中查找是否存在关键字 4 ，因数列不是有序的，所以不能使用二分查找，如果要使用二分查找算法，则需要先对数列进行排序。
二分查找使用了二分（折半）算法思想，二分查找算法中有 2 个关键信息需要随时获取：
现在通过在数列 nums=[1,3,4,5,8,10,12] 中查找关键字 8来了解二分查找的算法流程。
在进行二分查找之前，先定义 2 个位置（指针）变量：
第 1 步：通过左、右指针的当前位置计算出数列的中间位置 mid_pos=3，并根据 mid_pos 的值找出数列中间位置所对应的值 mid_val=nums[mid_pos] 是 5。
二分查找算法的核心就是要找出数列中间位置的值。
第 2 步：把数列中间位置的值和给定的关键字相比较。这里关键字是 8，中间位置的值是 5，显然 8 是大于 5，因为数列是有序的，自然会想到没有必要再与数列中 5 之前的数字比较，而是专心和 5 之后的数字比较。
一次比较后再次查找的数列范围缩小了一半。这也是二分算法的由来。
第 3 步：根据比较结果，调整数列的大小，这里的大小调整不是物理结构上调整，而是逻辑上调整，调整后原数列没有变化。也就是通过修改左指针或右指针的位置，从逻辑上改变数列大小。调整后的数列如下图。
二分查找算法中数列的范围由左指针到右指针的长度决定。
第 4 步：重复上述步骤，至到找到或找不到为止。
编码实现二分查找算法
''' 二分查找算法 ''' def binary_find(nums, key): # 初始左指针 l_idx = 0 # 初始在指针 r_ldx = len(nums) - 1 while l_idx <= r_ldx: # 计算出中间位置 mid_pos = (r_ldx + l_idx) // 2 # 计算中间位置的值 mid_val = nums[mid_pos] # 与关键字比较 if mid_val == key: # 出口一：比较相等，有此关键字，返回关键字所在位置 return mid_pos elif mid_val > key: # 说明查找范围应该缩少在原数的左边 r_ldx = mid_pos - 1 else: l_idx = mid_pos + 1 # 出口二：没有查找到给定关键字 return -1 ''' 测试二分查找 ''' if __name__ == "__main__": nums = [1, 3, 4, 5, 8, 10, 12] key = 3 pos = binary_find(nums, key) print(pos)
通过前面对二分算法流程的分析，可知二分查找的子问题和原始问题是同一个逻辑，所以可以使用递归实现：
''' 递归实现二分查找 ''' def binary_find_dg(nums, key, l_idx, r_ldx): if l_idx > r_ldx: # 出口一：没有查找到给定关键字 return -1 # 计算出中间位置 mid_pos = (r_ldx + l_idx) // 2 # 计算中间位置的值 mid_val = nums[mid_pos] # 与关键字比较 if mid_val == key: # 出口二：比较相等，有此关键字，返回关键字所在位置 return mid_pos elif mid_val > key: # 说明查找范围应该缩少在原数的左边 r_ldx = mid_pos - 1 else: l_idx = mid_pos + 1 return binary_find_dg(nums, key, l_idx, r_ldx) ''' 测试二分查找 ''' if __name__ == "__main__": nums = [1, 3, 4, 5, 8, 10, 12] key = 8 pos = binary_find_dg(nums, key,0,len(nums)-1) print(pos)
二分查找性能分析：
二分查找的过程用树形结构描述会更直观，当搜索完毕后，绘制出来树结构是一棵二叉树。
1.如上述代码执行过程中，先找到数列中的中间数字 5，然后以 5 为根节点构建唯一结点树。
2.5 和关键字 8 比较后，再在以数字 5 为分界线的右边数列中找到中间数字10，树形结构会变成下图所示。
3.10 和关键字 8比较后，再在10 的左边查找。
查找到8 后，意味着二分查找已经找到结果，只需要 3 次就能查找到最终结果。
从二叉树的结构上可以直观得到结论：二分查找关键字的次数由关键字在二叉树结构中的深度决定。
4.上述是查找给定的数字8，为了能查找到数列中的任意一个数字，最终完整的树结构应该如下图所示。
很明显，树结构是标准的二叉树。从树结构上可以看出，无论查找任何数字，最小是 1 次，如查找数字 5，最多也只需要 3 次，比线性查找要快很多。
根据二叉树的特性，结点个数为 n 的树的深度为 h=log2(n+1)，所以二分查找算法的大 o 表示的时间复杂度为 o(logn)，是对数级别的时间度。
当对长度为1000的数列进行二分查找时，所需次数最多只要 10 次，二分查找算法的效率显然是高效的。
但是，二分查找需要对数列提前排序，前面的时间复杂度是没有考虑排序时间的。所以，二分查找一般适合数字变化稳定的有序数列。
插值查找本质是二分查找，插值查找对二分查找算法中查找中间位置的计算逻辑进行了改进。
原生二分查找算法中计算中间位置的逻辑：中间位置等于左指针位置加上右指针位置然后除以 2。
# 计算中间位置 mid_pos = (r_ldx + l_idx) // 2
插值算法计算中间位置逻辑如下所示：
key 为要查找的关键字！！
# 插值算法中计算中间位置 mid_pos = l_idx + (key - nums[l_idx]) // (nums[r_idx] - nums[l_idx]) * (r_idx - l_idx)
编码实现插值查找：
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号