1. 查找表：是对同一类型的需要被查找的元素的集合，可以使用线性表、树表、散列表（哈希表），本节我们只讨论线性表
2. 关键字：在一个数据集合中，可以唯一标识一个数据的值就是该数据的关键字
3. 查找：根据给定值，通过某种算法在查找表中确定一个关键字，该关键字代表的数据和给定值相等，则称为“查找成功”，这个过程就是“查找”
4. 动态查找表、静态查找表：若在查找的过程中会修改（插入和删除）查找表则称为“动态查找表”，否则称为“静态查找表”（如果学习过C++的map或者set的[]用法，就更能理解“动态”的过程）
5. 平均查找长度：这是类似时间复杂度或空间复杂度的算法和衡量标志，不过更多针对查找算法，公式为$ASL = \sum_{i=1}^{n} (P_{i}C_{i})$，其中$P_{i}$ 是在表中查找第$i$个数据的概率，$C_{i}$是在查找过程中，第$i$个数据和已经比较过的关键字的个数，因此查找不同关键字会发送变化

接下来我们提及的查找算法都是在数组这样的查找表中查找数据，关于树表和散列表我在C++部分提及。

2.顺序查找法

顺序查找算法比较容易，基本就是依次遍历查找表中的所有元素，直到找到和给定值相同的数据即可。

2.1.不带哨兵位

//待补充...

2.2.带上哨兵位

//待补充...

3.二分查找法

这个算法本身不难理解，但是编写代码非常容易越界...

//待补充...

4.分块查找法

分块查找又被称为“索引顺序查找算法”，性能介于顺序算法和二分查找算法，为什么呢？实际上就是把一张表划分为多个子表，将每个子表中的最值作为子表的关键字，保证子表$T_1$内的所有元素都小于/大于$T_2$内的所有元素，并且以二分法的方式存储子表的关键字。

因此每次查找某一个数据，只需要根据二分法的思路查找表的关键字，再根据表的关键字和给定值的进行顺序查找。

//待补充...

更新日志

2025/11/20 09:51

查看所有更新日志

• 4e00a-初步修改完成，以集合的方式来推进文档项目于 2025/11/20
• 6e6aa-项目大更新于 2025/11/20
• 7ef8c-添加一些文件，同时做好一些基础的加密防护于 2025/11/16
• 01111-保存所有的学习于 2025/11/13
• 7ffa6-学习使用 Sentinel、Sa-token、Nacos、ES于 2025/4/19
• 1a85c-临时迁移文件，开始部署博客于 2025/4/9
• b7955-修改资源目录于 2025/4/2
• 1d7f9-数据备份于 2025/1/15
• 9c3ea-数据备份于 2025/1/14

版权所有

版权归属：limou3434

许可证：署名 4.0 国际 (CC-BY-4.0)