顺序查找
存储结构为顺序存储或链接存储的线性表
查找的时间复杂度为 $O(N)$
二分查找
元素必须是有序的
每次将目标值与中间节点的值进行比较，再判断其落入中间节点的左侧或右侧。
可以使用迭代或递归实现。
插值查找
二分查找进阶
联系查字典，将二分查找中的 $mid = \frac{low + high}{2}$ 修改为自适应的 $mid = low + (key - a[low]) / a[high] - a[low]) * (high -low)$ 及将二分查找中的比例 0.5 改为自适应的值，根据关键字在表中的位置，让下一次查找更靠近关键字，从而减少了查找的次数。
插值查找一般适用于表长较大，同时关键字分布较为均匀的表。
复杂度：$O(log_2(log_2n))$
斐波那契查找
类比二分查找，当表长等于某斐波那契数时使用。
最坏情况时间复杂度为 $O(log_2n)$，期望复杂度 $O(log_2n)$
二叉树查找
二叉搜索树的特点是左子节点小于父节点，父节点小于右子节点。
此方案的查找效率较高，但是需要维护二叉树，并且在查找树严重不平衡时退化为“链表”。
将二叉搜索树进行优化，可以参考平衡二叉树、红黑树。
平衡查找树
2-3 Tree
每个节点保存1个或2个值（对应可以拥有2个或3个子节点）
性质：在一个完全平衡的2-3查找树中，根节点到每一个叶节点的距离都相同。
红黑树
红黑树的思想是对2-3查找树进行编码，特别是对其中的3-node节点添加额外的信息。
可以想像两个红色边链接的节点对应2-3查找树中的3-node。
红黑树的定义：
- 红色节点向左倾斜；
- 一个节点不可能有两个红色连接；
- 根节点到每个叶节点的黑色链接个数相同。
红黑树的应用：
- Java:
Java.util.TreeMap,Java.util.TreeSet; - C++:
STL::map,STL::multimap,STL::multiset; - .NET:
SortedDictionary,SortedSet
B树
B树可以看作是2-3查找树的拓展，其每个节点允许有M-1个子节点
B树的定义
- 根节点至少有两个子节点
- 每个节点有M-1个key，并以升序排列
- 其他节点至少有 M/2 个子节点
基本操作演示动画：
B树的优点：
- 每一个节点包含 key 和 value， 因此经常访问的元素可能距离根节点更近，可以更快访问。
B+树
B+树的定义
- 有 k 个子节点的节点必然有 k 个关键码
- 非叶节点仅具有索引作用
- 叶节点存放记录相关的信息
- 树的所有叶节点构成一个有序链表，可以按照关键码排序的次序遍历全部记录
试想一下，在文件系统中，若该文件在磁盘上的分区恰好不属于同一个父节点，此时B+树与B树的性能差异
如下为B+树的操作动画：
B+树的优点：
- 内部节点不含数据信息，内存页可以存放更多的key。
- 数据存放紧密，具有更好的空间局部性，访问叶节点关联的数据具有更高的缓存命中率。
- 叶节点构成有序链表，对整棵树的遍历更快。
- 便于区间查找与搜索。（非同父节点时优势明显）
B树/B+树的应用：
- Windows: HPFS
- Mac: HFS, HFS+
- Linux: ResiserFS, XFX, Ext3FS, JFS
- 数据库: ORACLE, MySQL, SQLServer
分块查找
每一块中数据不必有序。 但快间数据有序。 （类比快排的中间步骤）
算法步骤：
- 选取各块中的最大关键字构成索引表
- 二分查找确定索引块
- 索引块内顺序查找目标值
哈希查找
哈希函数：使关键字分散到指定大小的顺序结构的转换关系。
算法流程：
- 使用哈希函数构造哈希表
- 解决地址冲突
- 拉链法
- 线性探测法
- 执行哈希查找