1.查找的基本概念
约 657 字大约 2 分钟
2025-06-21
- 查找表:是对同一类型的需要被查找的元素的集合,可以使用线性表、树表、散列表(哈希表),本节我们只讨论线性表
- 关键字:在一个数据集合中,可以唯一标识一个数据的值就是该数据的关键字
- 查找:根据给定值,通过某种算法在查找表中确定一个关键字,该关键字代表的数据和给定值相等,则称为“查找成功”,这个过程就是“查找”
- 动态查找表、静态查找表:若在查找的过程中会修改(插入和删除)查找表则称为“动态查找表”,否则称为“静态查找表”(如果学习过
C++的map或者set的[]用法,就更能理解“动态”的过程) - 平均查找长度:这是类似时间复杂度或空间复杂度的算法和衡量标志,不过更多针对查找算法,公式为ASL=∑i=1n(PiCi),其中Pi 是在表中查找第i个数据的概率,Ci是在查找过程中,第i个数据和已经比较过的关键字的个数,因此查找不同关键字会发送变化
接下来我们提及的查找算法都是在数组这样的查找表中查找数据,关于树表和散列表我在C++部分提及。
2.顺序查找法
顺序查找算法比较容易,基本就是依次遍历查找表中的所有元素,直到找到和给定值相同的数据即可。
2.1.不带哨兵位
//待补充...2.2.带上哨兵位
//待补充...3.二分查找法
这个算法本身不难理解,但是编写代码非常容易越界...
//待补充...4.分块查找法
分块查找又被称为“索引顺序查找算法”,性能介于顺序算法和二分查找算法,为什么呢?实际上就是把一张表划分为多个子表,将每个子表中的最值作为子表的关键字,保证子表T1内的所有元素都小于/大于T2内的所有元素,并且以二分法的方式存储子表的关键字。
因此每次查找某一个数据,只需要根据二分法的思路查找表的关键字,再根据表的关键字和给定值的进行顺序查找。
//待补充...更新日志
2025/11/20 09:51
查看所有更新日志