Python查找算法之插补查找算法的实现
作者:Amo Xiang 发布时间:2021-03-12 08:16:57
一、插补查找算法
插补查找算法又称为插值查找,它是折半查找算法的改进版。插补查找是按照数据的分布,利用公式预测键值所在的位置,快速缩小键值所在序列的范围,慢慢逼近,直到查找到数据为止。根据描述来看,插值查找类似于平常查英文字典的方法。例如,在查一个以字母 D 开头的英文单词时,决不会用折半查找法。根据英文词典的查找顺序可知,D 开头的单词应该在字典较前的部分,因此可以从字典前部的某处开始查找。键值的索引计算,公式如下:
middle=left+(target-data[left])/(data[right]-data[left])*(right-left)
参数说明:
middle:所求的边界索引。
left:最左侧数据的索引。
target:键值(目标数据)。
data[left]:最左侧数据值。
data[right]:最右侧数据值。
right:最右侧数据的索引。
例如,已经有排序好的数列:34、53、57、68、72、81、89、93、99。要查找的数据是 53,使用插补查找法步骤如下:
步骤1:将数据列出来并利用公式找到边界值,计算过程如下:
将各项数据带入公式:
将数据取整,因此所求索引是 2,对应的数据是 57,将查找目标数据 53 与 57 进行比较,如下图所示。
步骤2:将 53 与 57 进行比较,结果是 53 小于 57,所以查找 57 的左半边数据,不用考虑右半边的数据,索引范围缩小到 0 和 2 之间,公式带入:
取整之后索引是 1,对应的数据是 53,将查找目标数据 53 与 53 进行比较,如下图所示:
步骤3:将 53 与 53 进行比较,所得结果相等,查找完成。说明:如果多次分割之后没有找到相等的值,表示这个键值没有在这个数列中。
通过上述的步骤1就能看出,插补查找算法比折半查找算法的取值范围更小,因此它的速度要比折半法查找快,这就是插补查找算法的优点。
二、实例:利用插补查找用户输入的数据
用户可以随意输入一组数据,例如本实例输入一组数据:34、53、57、68、72、81、89、93、99。在这组数据中用插补查找法分别查找数据 57、53、93、89、100,且显示每次查找的过程。用 Python 代码实现此过程,具体代码如下:
def insert_search(data, num):
"""
自定义查找函数:该函数使用的是插补查找算法
:param data: 原数列data
:param num: 键值num
:return:
"""
# 计算
left_index = 0 # 最左侧数据的索引
right_index = len(data) - 1 # 最右侧数据的索引
print("正在查找.......") # 提示
while left_index <= right_index:
# 使用公式计算出索引值
middle = left_index + (num - data[left_index]) / (data[right_index] - data[left_index]) * (
right_index - left_index)
# 取整
middle = int(middle)
# print(middle)
if num == data[middle]:
return middle # 如果键值等于边界值,返回边界位置
elif num < data[middle]:
# 输出位置在数列中的左半边
print(f"{num} 介于位置{left_index + 1}[{data[left_index]}]和边界值{middle + 1}[{data[middle]}]之间,找左半边......")
right_index = middle - 1 # 如果键值小于边界值,最右边数据索引等于边界位置减1
else:
# 输出位置在数列中的左半边
print(f"{num} 介于位置{middle + 1}[{data[middle]}]和边界值{right_index + 1}[{data[right_index]}]之间,找右半边......")
left_index = middle + 1 # 如果键值大于边界值,最左边数据索引等于边界位置加1
return -1 # 自定义函数到此结束
inp_num = 0 # 定义变量,用来输入键值
num_list = [34, 53, 57, 68, 72, 81, 89, 93, 99] # 定义数列
print("数据内容是:")
for index, ele in enumerate(num_list):
print(f" {index + 1}[{ele}]", end="") # 输出数列
print("")
flag = True # 开关,用来管控是否多次查找
while flag: # 循环查找
inp_num = int(input("请输入要查找的键值:").strip()) # 输入查找键值
result = insert_search(num_list, inp_num) # 调用自定义的查找函数——insert_search()函数
if result == -1: # 判断查找结果是否是-1
print(f"没有找到[{inp_num}]") # 若为-1,提示没有找到值
else:
# 若不为-1,提示查找位置
print(f"在{result + 1}个位置找到[{inp_num}]")
char = input("本次查找结束,是否继续查找,请输入 y(Y) 或 n(N):").strip()
if char.upper() == "N":
flag = False
程序执行结果如下图所示:
来源:https://blog.csdn.net/xw1680/article/details/115406312
猜你喜欢
- 首先要注册一个账号密码,通过账号密码登录,并且滑块验证,自动输入搜索关键词,进行跳转翻页爬取数据,并保存到Excel文件中。代码运行时,滑块
- 对会读书的人来说,读一本书要做的第一件事,就是仔细阅读这本书的目录。阅读目录可以对整体内容有所了解,并清楚地知道感兴趣的部分在哪里,提高阅读
- 有一组4096长度的数据,需要找到一阶导数从正到负的点,和三阶导数从负到正的点,截取了一小段。394.0 388.0 389.0 388.0
- 概要本文分步介绍了如何在运行 SQL Server 的计算机之间移动 Microsoft SQL Server 用户数据库和大多数常见的 S
- css的流行导致了标签的流行,很直观,看起来很清爽。流行的一部分,还有很多种功能强大且美观的导航。。。1. Change.org2. N.D
- 一. 介绍一个计数器工具提供快速和方便的计数,Counter是一个dict的子类,用于计数可哈希对象。它是一个集合,元素像字典键(key)一
- 使用ASP做网站虽然有点落伍,但在中国还是有很大市场的,因为大部分国内用户使用Windows Server服务器,在Windows Serv
- 安装模块下面需要用模块,先安装一下:pip install numpy pip install opencv-python==4.5.5.6
- 对于刚刚学习编程的同学来说对编程是非常陌生的,对很多的代码也是非常陌生,高中忙于学习的我们甚至可以说是对编程是一无所知,进入大学进入到这个专
- APScheduler (advanceded python scheduler)是一款Python开发的定时任务工具。文档地址
- 如果你的PHP网站换了空间,必定要对Mysql数据库进行转移,一般的转移的方法,是备份再还原,有点繁琐,而且由于数据库版本的不一样会导致数据
- Python socket C/S结构的聊天室应用服务端:#!/usr/bin/env python#coding:utf8 import
- 相关验证码文章:asp制作验证码的方法 轩魂ASP中文验证码下载 先产生一个4位数的随机码源代码:ychar="0,1,2,3,4
- 昨时要导一些数据,从网上搜到的。字段多时insert 语句生成的不完整了,还没有找到原因..有个缺点……就是标识种子的列 也insert了c
- 最近和一程序员合作项目。弄的我头都大了~埋怨我的CSS命名看不懂~得按照他的来。结果我打开他的页面,看了看,从头第一个开始就是content
- Pattern.split方法详解/** * 测试Pattern.split方法 */ @Test public void testPatt
- 用过jQuery的朋友一定对jQuery中方法的链式调用印象深刻,最近发布的YUI3也支持了方法的链式调用。这是一个非常不错的语法特性,能让
- IE(internet explorer)公司:微软(MicroSoft)布局引擎:Trident(也做MSHTML)注:解析渲染
- 做项目的时候,一位同事导数据的时候,不小心把一个表中的数据全都搞重了,也就是说,这个表里所有的记录都有一条重复的。这个表的数据是千万级的,而
- 主要内容所谓RPC,是远程过程调用(Remote Procedure Call)的简写,网上解释很多,简单来说,就是在当前进程调用其他进程的