算法 查找
一、定义
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。查找按照操作方式可分为：
- 静态查找 ：只做查找操作
- 动态查找 ：在查找中同时进行插入或删除等操作
二、顺序查找
又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。该算法的时间复杂度为 O(n)。基本思路是从第一个元素 m 开始逐个与需要查找的元素 x 进行比较，当比较到元素值相同 (即 m =x) 时返回元素 m 的下标，如果比较到最后都没有找到，则返回 -1。
- 缺点：是当 n 很大时，平均查找长度较大，效率低；
- 优点：是对表中数据元素的存储没有要求；另外，对于线性链表，只能进行顺序查找。
三、二分查找
是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种查找算法每一次比较都使查找范围缩小一半，时间复杂度为 O(logn) 。
- 比较次数少，查找速度快，平均性能好
- 要求 待查表为有序表 ，且插入删除困难。
四、插值查找
折半查找这种查找方式，不是自适应的（中间点是固定的）。二分查找中查找点计算如下：
mid=(low+high)/2, 即mid=low+1/2*(high-low)通过类比，我们可以将查找的点改进为如下方式：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。
- 适用于关键字分布比较均匀的有序表
- 如果关键字分布非常不均匀，很可能不如二分查找
五、斐波那契查找
在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数 F[n]，将原查找表扩展为长度为 F n，完成后进行斐波那契分割，即 F[n]个元素分割为前半部分 F[n-1]个元素，后半部分 F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
六、分块查找
分块查找又称索引顺序查找，它是顺序查找的一种改进方法。将 n 个数据元素 "按块有序" 划分为 m 块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须 "按块有序"；即第 1 块中任一元素的关键字都必须小于第 2 块中任一元素的关键字；而第 2 块中任一元素又都必须小于第 3 块中的任一元素，……，基本流程：
- 先选取各块中的最大关键字构成一个索引表；
- 先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。
七、哈希查找
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为 O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。算法流程：
- 用给定的哈希函数构造哈希表
- 根据选择的冲突处理方法解决地址冲突
- 在哈希表的基础上执行哈希查找
八、树表查找
1、二叉查找树
二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。对二叉查找树进行中序遍历，即可得到有序的数列。
- 如果经常动态查找，可以使用平衡二叉树
2、2- 3 查找树
和二叉树不一样，2- 3 树运行每个节点保存 1 个或者两个的值。对于普通的 2 节点 (2-node)，他保存 1 个 key 和左右两个自己点。对应 3 节点(3-node)，保存两个 Key，可以有效降低树的高度，增加查找速率。如果中序遍历 2 - 3 查找树，就可以得到排好序的序列。
3、红黑树
2- 3 查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是 2 -node，树的高度为 lgn，从而保证了最坏情况下的时间复杂度。但是 2 - 3 树实现起来比较复杂，于是就有了一种简单实现 2 - 3 树的数据结构，即红黑树，红黑树的思想就是对 2 - 3 查找树进行编码，尤其是对 2 - 3 查找树中的 3 -nodes 节点添加额外的信息。
4、B 树和 B + 树
B 树可以看作是对 2 - 3 查找树的一种扩展，即他允许每个节点有 M - 1 个子节点，B 树，概括来说是一个节点可以拥有多于 2 个子节点的二叉查找树。
B 和 B + 树的区别在于，B+ 树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历
但是 B 树也有优点，其优点在于，由于 B 树的每一个节点都包含 key 和 value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。