当前位置:网站首页>线性表的查找
线性表的查找
2022-07-06 20:15:00 【ScarboroughFair#】
目录
1.顺序表查找算法
顺序查找的实现
改进:运用&,for循环后面加上分号
改进:把待查关键字key存入表头(哨兵),从后往前逐个比较,可以免去查找过程中每一步都要检测是否查找完毕,加快速度
当ST.length较大时,此改进能使进行一次查找所需的平均时间几乎减少一半
(带哨兵)顺序查找时间效率分析
顺序查找的特点
2.二分查找(详细见专栏:Acwing基础课)
二分查找的实现
普通折半查找
二分查找的递归算法
二分查找的性能分析——判定树
时间复杂度 O(logn)
二分查找特点
对线性链表无效的原因是找不到mid
3.分块查找
分块查找的实现
条件:1.将表分成几块,且表或者有序,或者分块有序;若i<j,则第j块中所有记录的关键字均大于第i块中的最大关键字
2.建立“索引表”(每个结点含有最大关键字和指向本块第一个结点的指针,且按关键字有序)
分块查找性能分析
分块查找特点
4.插值查找(了解)
5. 斐波那契查找
int Fibonacci_Search(int* a, int n, int key)
{
int low, high, mid, i, k;
low = 1; //定义最低下标为记录首位
high = n; //定义最高下标为记录末位
k = 0;
while (n > F[k] - 1) //计算n位于斐波那契数列的位置
k++;
for (i = n; i < F[k] - 1; i++) //将不满的数值补全
a[i] = a[n];
while (low <= high)
{
mid = low + F[k - 1] - 1; //计算当前分隔的下标
if (key < a[mid]) //若查找记录小于当前分隔记录
{
high = mid - 1; //最高下标调整到分割下标mid-1处
k = k - 1; //斐波那契数列下标减一位
}
else if (key > a[mid]) //若查找记录大于当前分隔记录
{
low = mid + 1; //最低下标调整到分隔下标mid+1处
k = k - 2; //斐波那契数列下标减两位
}
else
{
if (mid <= n)
return mid; //若相等则说明mid即为查找到的位置
else
return n; //若mid>n,说明是补全数值,返回n
}
}
return 0;
}
边栏推荐
- Jericho turns on the display icon of the classic Bluetooth hid mobile phone to set the keyboard [chapter]
- Appx代码签名指南
- The version control of 2021 version is missing. Handling method
- 2022 information security engineer examination outline
- 你知道电子招标最突出的5大好处有哪些吗?
- HDU ACM 4578 Transformation-&gt; Segment tree - interval change
- Development of wireless communication technology, cv5200 long-distance WiFi module, UAV WiFi image transmission application
- Significance and measures of source code confidentiality
- [cpk-ra6m4 development board environment construction based on RT thread studio]
- Flutter3.0了,小程序不止于移动应用跨端运行
猜你喜欢
Household appliance industry under the "retail is king": what is the industry consensus?
Don't you know the relationship between JSP and servlet?
函数重入、函数重载、函数重写自己理解
leetcode
Le tube MOS réalise le circuit de commutation automatique de l'alimentation principale et de l'alimentation auxiliaire, et la chute de tension "zéro", courant statique 20ua
“去虚向实”大潮下,百度智能云向实而生
How-PIL-to-Tensor
尚硅谷JVM-第一章 类加载子系统
Intelligent static presence detection scheme, 5.8G radar sensing technology, human presence inductive radar application
掘金量化:通过history方法获取数据,和新浪财经,雪球同用等比复权因子。不同于同花顺
随机推荐
掘金量化:通过history方法获取数据,和新浪财经,雪球同用等比复权因子。不同于同花顺
[swift] learning notes (I) -- familiar with basic data types, coding styles, tuples, propositions
LAB1配置脚本
Jerry's question about DAC output power [chapter]
如何分析粉丝兴趣?
Jerry's broadcast has built-in flash prompt tone to control playback pause [chapter]
Opencv environment, and open a local PC camera.
你知道电子招标最突出的5大好处有哪些吗?
简单冒泡排序
Netperf and network performance measurement
2022.6.28
Domcontentloaded and window onload
商城商品的知识图谱构建
装饰设计企业网站管理系统源码(含手机版源码)
HDU ACM 4578 Transformation-&gt; Segment tree - interval change
Shangsilicon Valley JVM Chapter 1 class loading subsystem
leetcode
知识图谱构建全流程
Numpy中排序操作partition,argpartition,sort,argsort
Error: could not find a version that satisfies the requirement xxxxx (from versions: none) solutions