python 线性插值,

  python 线性插值,

  本文主要介绍了Python中四种常用搜索算法的实现:线性、二进制、分块和插值。通过图片详细讲解了它们实现的原理和代码,有需要的可以参考。

  00-1010 1.线性搜索2。二分搜索法3。插值搜索4。封锁搜索5。摘要搜索算法用于搜索给定数据(关键字)是否存在于序列数据(总体)中。常用的搜索算法有:

  线性搜索:线性搜索也称为顺序搜索,用于在无序序列中进行搜索。二分搜索法:二分搜索法也叫二分搜索法,它的算法用于有序序列。插值搜索:插值搜索是二分搜索法算法的改进。块搜索:也称为索引顺序搜索,是线性搜索的改进版本。树表搜索:树表搜索可分为二叉查找树和平衡二叉树搜索。哈希搜索:哈希搜索可以直接通过关键字找到需要的数据。因为树表查找和哈希查找需要更多的空间,所以在本文中不做解释。本文将详细介绍除树表和hash之外的搜索算法,分析每种算法的优缺点,并提出相应的优化方案。

  

目录

  线性搜索也叫顺序搜索,属于原始的、穷举的、暴力的搜索算法。易于理解,编码简单。但当数据量较大时,由于其算法思想简单穷举,算法中优化设计不多,性能会很低。

  线性搜索思想:

  从头到尾逐个扫描原始列表中的每个数据,并与给定的关键字进行比较。如果比较结果相等,则搜索成功。当扫描完成时,仍然没有找到与给定关键字等同的数据,则搜索被宣布为失败。根据对线性搜索算法的描述,很容易编码和实现:

  线性搜索算法

  参数:

  Nums:序列

  Key:关键字

  返回值:

  关键字在序列中的位置

  如果不是,返回-1。

  def line_find(nums,key):

  对于范围内的I(len(nums)):

  if nums[i]==key:

  返回I

  返回-1

  测试线性算法

  if __name__==__main__:

  nums=[4,1,8,10,3,5]

  Key=int(input(请输入您要查找的关键字:))

  pos=line_find(nums,key)

  Print(关键字{0}位于序列中的第{1}个位置)。格式(键、位置))

  输出结果:

  请输入您要查找的关键字:3

  关键字3在序列的位置4。

  线性搜索算法的平均时间复杂度分析。

  1.最幸运的情况:如果要搜索的关键词恰好在序列的第一个位置,只需要搜索一次。

  例如,在序列=[4,1,8,10,3,5]中搜索关键字4。

  你只需要查一次。

  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的存在。

  扫描了六遍,我被打败了!

  改良线性查找算法

  可以相应地优化线性搜索算法。如设立“前哨”。所谓“前哨”,就是在搜索之前,把要搜索的关键字插入到序列的末尾。

  def line_find_(nums,key):

  i=0

  while nums[i]!=key:

  i=1

  返回-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指令集。

  有一种优化方案就是减少编译后的指令集。

  

  

2. 二分查找

  二分查找属于有序查找,所谓有序查找,指被查找的数列必须是有序的。如在数列=[4,1,8,10,3,5,12]中查找是否存在关键字4,因数列不是有序的,所以不能使用二分查找,如果要使用二分查找算法,则需要先对数列进行排序。

  二分查找使用了二分(折半)算法思想,二分查找算法中有2个关键信息需要随时获取:

  

  • 一个是数列的中间位置mid_pos。
  • 一个是数列的中间值mid_val。

  现在通过在数列nums=[1,3,4,5,8,10,12]中查找关键字8来了解二分查找的算法流程。

  在进行二分查找之前,先定义2个位置(指针)变量:

  

  • 左指针l_idx初始指向数列的最左边数字。
  • 右指针r_idx初始指向数列的最右边数字。

  

  第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次,二分查找算法的效率显然是高效的。

  但是,二分查找需要对数列提前排序,前面的时间复杂度是没有考虑排序时间的。所以,二分查找一般适合数字变化稳定的有序数列。

  

  

3. 插值查找

  插值查找本质是二分查找,插值查找对二分查找算法中查找中间位置的计算逻辑进行了改进。

  原生二分查找算法中计算中间位置的逻辑:中间位置等于左指针位置加上右指针位置然后除以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)

  

  编码实现插值查找:

  

# 插值查找基于二分法,只是mid计算方法不同

  def binary_search(nums, key):

   l_idx = 0

   r_idx = len(nums) - 1

   old_mid = -1

   mid_pos = None

   while l_idx < r_idx and nums[0] <= key and nums[r_idx] >= key and old_mid != mid_pos:

   # 中间位置计算

   mid_pos = l_idx + (key - nums[l_idx]) // (nums[r_idx] - nums[l_idx]) * (r_idx - l_idx)

   old_mid = mid_pos

   if nums[mid_pos] == key:

   return "index is {}, target value is {}".format(mid_pos, nums[mid_pos])

   # 此时目标值在中间值右边,更新左边界位置

   elif nums[mid_pos] < key:

   l_idx = mid_pos + 1

   # 此时目标值在中间值左边,更新右边界位置

   elif nums[mid_pos] > key:

   r_idx = mid_pos - 1

   return "Not find"

  li =[1, 3, 4, 5, 8, 10, 12]

  print(binary_search(li, 6))

  

  插值算法的中间位置计算时,对中间位置的计算有可能多次计算的结果是一样的,此时可以认为查找失败。

  插值算法的性能介于线性查找和二分查找之间。

  当数列中数字较多且分布又比较均匀时,插值查找算法的平均性能比折半查找要好的多。如果数列中数据分布非常不均匀,此种情况下插值算法并不是最好的选择。

  

  

4. 分块查找

  分块查找类似于数据库中的索引查询,所以分块查找也称为索引查找。其算法的核心还是线性查找。

  现有原始数列nums=[5,1,9,11,23,16,12,18,24,32,29,25],需要查找关键字11是否存在。

  第1步:使用分块查找之前,先要对原始数列按区域分成多个块。至于分成多少块,可根据实际情况自行定义。分块时有一个要求,前一个块中的最大值必须小于后一个块的最小值。

  块内部无序,但要保持整个数列按块有序。

  

  分块查找要求原始数列从整体上具有升序或降序趋势,如果数列的分布不具有趋向性,如果仍然想使用分块查找,则需要进行分块有序调整。

  第2步:根据分块信息,建立索引表。索引表至少应该有2个字段,每一块中的最大值数字以及每一块的起始地址。显然索引表中的数字是有序的。

  

  第3步:查找给定关键字时,先查找索引表,查询关键字应该在那个块中。如查询关键字29,可知应该在第三块中,然后根据索引表中所提供的第三块的地址信息,再进入第三块数列,按线性匹配算法查找29具体位置。

  

  编码实现分块查找:

  先编码实现根据分块数量、创建索引表,这里使用二维列表保存储索引表中的信息。

  

  分块:建立索引表

  参数:

   nums 原始数列

   blocks 块大小

  def create_index_table(nums, blocks):

   # 索引表使用列表保存

   index_table = []

   # 每一块的数量

   n = len(nums) // blocks

   for i in range(0, len(nums), n):

   # 索引表中的每一行记录

   tmp_lst = []

   # 最大值

   tmp_lst.append(max(nums[i:i + n-1]))

   # 起始地址

   tmp_lst.append(i)

   # 终止地址

   tmp_lst.append(i + n - 1)

   # 添加到索引表中

   index_table.append(tmp_lst)

   return index_table

  测试分块

  nums = [5, 1, 9, 11, 23, 16, 12, 18, 24, 32, 29, 25]

  it = create_index_table(nums, 3)

  print(it)

  输出结果:

  [[11, 0, 3], [23, 4, 7], [32, 8, 11]]

  

  代码执行后,输出结果和分析的结果一样。

  以上代码仅对整体趋势有序的数列进行分块。如果整体不是趋向有序,则需要提供相应块排序方案,有兴趣者自行完成。

  如上代码仅为说明分块查找算法。

  分块查找的完整代码:

  

  分块:建立索引表

  参数:

   nums 原始数列

   blocks 块大小

  def create_index_table(nums, blocks):

   # 索引表使用列表保存

   index_table = []

   # 每一块的数量

   n = len(nums) // blocks

   for i in range(0, len(nums), n):

   tmp_lst = []

   tmp_lst.append(max(nums[i:i + n - 1]))

   tmp_lst.append(i)

   tmp_lst.append(i + n - 1)

   index_table.append(tmp_lst)

   return index_table

  使用线性查找算法在对应的块中查找

  def lind_find(nums, start, end):

   for i in range(start, end):

   if key == nums[i]:

   return i

   break

   return -1

  测试分块

  nums = [5, 1, 9, 11, 23, 16, 12, 18, 24, 32, 29, 25]

  key = 16

  # 索引表

  it = create_index_table(nums, 3)

  # 索引表的记录编号

  pos = -1

  # 在索引表中查询

  for n in range(len(it) - 1):

   # 是不是在第一块中

   if key <= it[0][0]:

   pos = 0

   # 其它块中

   if it[n][0] < key <= it[n + 1][0]:

   pos = n + 1

   break

  if pos == -1:

   print("{0} 在 {1} 数列中不存在".format(key, nums))

  else:

   idx = lind_find(nums, it[pos][1], it[pos][2] + 1)

   if idx != -1:

   print("{0} 在 {1} 数列的 {2} 位置".format(key, nums, idx))

   else:

   print("{0} 在 {1} 数列中不存在".format(key, nums))

  输出结果

  16 在 [5, 1, 9, 11, 23, 16, 12, 18, 24, 32, 29, 25] 数列的第 5 位置

  

  分块查找对于整体趋向有序的数列,其查找性能较好。但如果原始数列整体不是有序,则需要提供块排序算法,时间复杂度没有二分查找算法好。

  分块查找需要建立索引表,这也需要额外的存储空间,其空间复杂度较高。其优于二分的地方在于只需要对原始数列进行部分排序。本质还是以线性查找为主。

  

  

5. 总结

  本文讲解了线性、二分、插值、分块查找算法。除此之外,还有其它如树表查找、哈希查找等算法。

  分块算法可认为是对线性查找算法的优化。

  插值查找可认为是在二分算法基础上的一个变化。

  算法没有固定模式,如果学会了二分查找算法,则认为是学会了一招,需要学会领悟,然后再在这一招上演变出更多变化。

  以上就是详解Python查找算法的实现(线性,二分,分块,插值)的详细内容,更多关于Python查找算法的资料请关注盛行IT软件开发工作室其它相关文章!

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: