1. 概述
查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的
数据元素。
查找表按照操作方式分为：静态查找表和动态查找表。
- 静态查找表：只作查找操作的查找表
- 动态查找表：在查找的过程中，会同时的插入查找表中不存在的数据元素，或者删除已经存在的某个元素
2. 顺序查找
最基本的查找技术，适合于存储结构为顺序存储或者链式存储的线性表，时间复杂度为O（n）
int sequence_search(int a[],int n, int key)
{
for (int i = 0; i < n; i++)
{
if (key == a[i]){
return i;
}
}
return -1;
}
3. 有序查找
- 二分查找
又称为折半查找，前提条件是线性表中的记录必须是有顺序的，即采用顺序存储，时间复杂度为O（logn）。基本思想为：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；反之，则在中间记录的右半区继续查找，不断重复上述步骤直至查找成功。
int binary_search(int a[], int n, int key)
{
int low = 0;
int high = n - 1;
int mid;
while (low < high)
{
mid = (low + high) / 2;
if (key == a[mid])
{
return mid;
}
else if (key < a[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}
插值查找
原先的，mid = low + ½（high - low），
改进为，mid = low + (key - a[low]) / (a[high] - a[low]) (high - low)
基本思想为：插值查找是根据要查找的关键字key与查找表中的最大最小记录的关键字比较后的查找方法。从时间复杂度来看为O（logn），但是其平均性能要比折半查找好很多。斐波那契查找
利用斐波那契数列的黄金分割原理来实现。
改进为，mid = low + F[k-1] - 1,其中k为斐波那契数列的下标，F[k-1]为斐波那契数列。
4. 线性索引查找
索引就是把一个关键字与它对应的记录相关联的过程。这里主要关注三种线性索引：稠密索引、分块索引、倒排索引。
稠密索引
在线性索引中，将数据集中的每个记录对应一个索引项，且索引项是按照关键码有序的排列。因此可以使用折半、插值、斐波那契等有序查找法，提高效率，但是空间代价比较高。-
分块索引
将数据集的记录分成了若干块，并且这些块需要满足两个条件：- 块内无序
- 快间有序
因此，查找分为两个步骤进行：①在分块索引表中查找关键字所在的块；②在相应的块中顺序查找关键码。分块索引普遍被用于数据库查找等技术的应用当中。
倒排索引
5. 树查找
- 二叉排序树
- AVL树
- 红黑树
- B/B+树
关于树查找请参考：树
6. 哈希查找
- 定义
在记录的存储位置和其关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。其中，f为哈希函数，记录存储的连续的存储空间称为哈希表。 - 查找步骤
- 存储时，通过哈希函数计算哈希地址，并存储
- 查找时，通过哈希函数计算哈希地址，并访问
- 哈希函数
好的哈希函数的原则：计算简单、哈希地址分布均匀- 直接定址法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
- 随机数法
- 处理哈希冲突的方法
两个关键字key1 ≠ key2，但是却出现f(key1) = f(key2),称这种现象为冲突。解决冲突的方法有：- 开放定址法
一旦发生了冲突，就去寻找下一个空的散列地址 - 再散列函数法
- 链地址法
- 公共溢出区法
- 开放定址法
- 实现
7. 参考
大话数据结构 ---- 程杰
