静态查找算法:仅对查找表进行查找操作,不改变表
一、顺序查找
算法思想:从表的一端开始,向另一端逐个按给定值kx与关键字进行比较,若找到,查找成功,并返回位置;若检测完毕,仍未找到,返回错误信息。
算法的时间复杂度:o(n)
优点:对表中数据的存储没有要求,线性链表只能进行顺序查找
缺点:当n很大时,平均查找长度达,效率低。
package com;
public class Find {
public static void main(String args[]){
//数组
int find[] = {1,3,6,9,7,5,8};
int stat = findKey(find,3);
System.out.println(stat);
int stat2 = findKeyR(find,78);
System.out.println(stat2);
}
//顺序查找,从前往后,查找失败返回长度
public static int findKey(int _find[], int key){
int len = _find.length;
int i;
for(i = 0; i < len && _find[i] != key;i++);
return i;
}
//顺序查找,从后往前,查找失败返回-1
public static int findKeyR(int _find[], int key){
int len = _find.length;
int i;
for(i = len-1; i >= 0 && _find[i] != key;i--);
return i;
}
}
二、折半查找(二分查找
)
折半查找是针对有序表的,即表中的数据元素按关键字升序或降序排列的表。
前提要求:1.必须采用顺序存储结构 2.必须按关键字大小有序排列
算法的时间复杂度:o(log(n))
优点:比较次数少,查找速度快,平均性能好;
缺点:要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
算法思想:
首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
package com;
public class Search {
public static void main(String args[]){
//数组
int find[] = {1,3,6,7,8,12,23};
int stat = BinarySearch(find,12);
System.out.println(stat);
}
//折半查找
public static int BinarySearch(int _find[], int key){
int len = _find.length;
//设定返回值,失败时返回-1;
int flag = -1;
//区间下界
int low = 0;
//区间上界
int high = len-1;
//中间位置
int mid;
while(low <= high){
mid = (low + high)/2;
if(_find[mid] < key){
low = mid + 1;
}else if(_find[mid] > key){
high = mid - 1;
}else{
flag = mid;
break;
}
}
return flag;
}
}
三、其他查找
插值查找
:也是针对有序表的,和二分插值的区别是,mid的取值规则
mid = low+(key-array[low])*(high-low)/(array[high]-array[low])
平均性能最好,只适合关键字平均分布的表 ,算法的时间复杂度:o(log(n))
分块查找:
又称索引顺序查找,是对顺序查找的改进。
算法思想:将查找表分为若干个子表,每个子表分块有序,对子表建立索引表,查找表的每一个子表由索引表中的索引项确定。
(1)首先用给定值key在索引表中检测索引项,以确定所要进行的查找在查找表中的查找分块,索引表关键字有序,可使用折半查找;
(2)对该分块进行顺序查找。
平均查找长度:索引表的平均长度和子表的平均长度的和。
m个数据元素,n个子表, 平均查找长度为(m+n/m)/2+1,当m=sqrt(n)时平均长度最小。
分享到:
相关推荐
神经网络与量子计算的交叉研究.pptx
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
【Ruby】基于Ruby的MKS rebase脚本 Ruby语言基础 将MKS网盘中其他工程路径下的工程文件批量rebase到目标工程路径。 【Ruby】基于Ruby的MKS rebase脚本 Ruby语言基础
18.CSGO赛事管理系统的设计与实现|Springboot+ Mysql+Java+ B/S结构(可运行源码(含数据库脚本)+开发文档+lw(高分毕设项目) 详细介绍链接:http://t.csdnimg.cn/CDBjW 内容概要: 全套项目源码+详尽文档,一站式解决您的学习与项目需求。 适用人群: 计算机、通信、人工智能、自动化等专业的学生、老师及从业者。 使用场景及目标: 无论是毕设、期末大作业还是课程设计,一键下载,轻松部署,助您轻松完成项目。 项目代码经过调试测试,确保直接运行,节省您的时间和精力。 其他说明: 项目整体具有较高的学习借鉴价值,基础能力强的可以在此基础上修改调整,以实现不同的功能。
46.书籍学习平台的设计与实现|Springboot+ Mysql+Java+ B/S结构(可运行源码+数据库+设计文档)论坛,公告,付费专区,免费专区,销售,会员办理,书籍分类 详细设计文档链接:http://t.csdnimg.cn/GSeDN 内容概要: 全套项目源码+详尽文档,一站式解决您的学习与项目需求。 适用人群: 计算机、通信、人工智能、自动化等专业的学生、老师及从业者。 使用场景及目标: 无论是毕设、期末大作业还是课程设计,一键下载,轻松部署,助您轻松完成项目。 项目代码经过调试测试,确保直接运行,节省您的时间和精力。 其他说明: 项目整体具有较高的学习借鉴价值,基础能力强的可以在此基础上修改调整,以实现不同的功能。
【资源说明】 基于OpenCVTensorflow的银行卡号识别源码+使用文档+全部资料(优秀项目).zip基于OpenCVTensorflow的银行卡号识别源码+使用文档+全部资料(优秀项目).zip基于OpenCVTensorflow的银行卡号识别源码+使用文档+全部资料(优秀项目).zip 【备注】 1、该项目是个人高分毕业设计项目源码,已获导师指导认可通过,答辩评审分达到95分 2、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 3、本项目适合计算机相关专业(如软件工程、计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载使用,也可作为毕业设计、课程设计、作业、项目初期立项演示等,当然也适合小白学习进阶。 4、如果基础还行,可以在此代码基础上进行修改,以实现其他功能,也可直接用于毕设、课设、作业等。 欢迎下载,沟通交流,互相学习,共同进步!
AI快速生成原创音乐的平台.txt
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
xiuno模板知乎蓝魔改版源码附多个插件
C语言诞生于美国的贝尔实验室,由丹尼斯·里奇(Dennis MacAlistair Ritchie)以肯尼斯·蓝·汤普森(Kenneth Lane Thompson)设计的B语言为基础发展而来,在它的主体设计完成后,汤普森和里奇用它完全重写了UNIX,且随着UNIX的发展,c语言也得到了不断的完善。为了利于C语言的全面推广,许多专家学者和硬件厂商联合组成了C语言标准委员会,并在之后的1989年,诞生了第一个完备的C标准,简称“C89”,也就是“ANSI C”,截至2020年,最新的C语言标准为2018年6月发布的“C18”。 [5] C语言之所以命名为C,是因为C语言源自Ken Thompson发明的B语言,而B语言则源自BCPL语言。 1967年,剑桥大学的Martin Richards对CPL语言进行了简化,于是产生了BCPL(Basic Combined Programming Language)语言。
FS-S01059_STEP_01A.zip
android 源码学习. 资料部分来源于合法的互联网渠道收集和整理,供大家学习参考与交流。本人不对所涉及的版权问题或内容负法律责任。如有侵权,请通知本人删除。感谢CSDN官方提供大家交流的平台
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。
基于深度强化学习的住宅区电动汽车充电策略是一种用于优化住宅区电动汽车充电行为的算法。面对日益增长的电动汽车数量和有限的充电资源,该算法结合了深度学习和强化学习方法,旨在实现住宅区电动汽车充电的智能调度和管理。
第5章 s7200编程语言及指令系统.ppt
1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。