很简单的东西，但是如果不去看的话，就很容易忘记，所以一定要复习一下，不然不会就很可惜。主要梳理一下相关的知识线，然后牛客的题目错题整一整。
参考：https://blog.csdn.net/fafawf/article/details/81457650
ASL参考：https://www.cnblogs.com/ygsworld/p/10238729.html
在华为面试的时候，面试官问了我一下知道查找算法都有哪些吗，我蒙了，又问索引查找和哈希查找的区别是什么，我又蒙了。这些其实都是很简单的东西啊，虽然很简单，但是你忘了就啥都不懂，显得很白痴。其实在查找中，最难的是数表查找。。。平均查找长度，KMP算是查找的内容。字符串匹配。
一.总概
七种查找算法其实可以分成4类，顺序查找和分块（索引）查找是一类，二分查找、插值查找、斐波那契查找是一类，树表是一类，哈希查找是一类。问题经常问的是平均查找长度，查找的最大次数之类的，最常考察的查找算法是二分查找。
顺序查找就是一个一个去找，分块就是先分成几个部分，然后索引是几个块的最大值，先找在哪个块，然后再用顺序查找。二分查找这一类是跳着找，只不过看怎么跳的，二分顾名思义就是找那一半的值。插值就是不一定找一半啊，改成自适应了。斐波那契就是取黄金比例的点的值，0.618。数表查找是属于动态查找的，就是先建树，再查找，细展开包括，二叉树，然后是自平衡二叉树（2-3树，红黑树，B树还有B+树）。最后一类是哈希查找。就是首先通过一个映射函数把数组映射成一个表中的key，然后value就是这个值。每次要找某个值时，把这个值映射一下，然后对应key，value就是要找的那个数。
复杂度：
二.顺序查找
很常见的就是问顺序查找的平均查找长度：成功的ASL为（n+1）/2。失败的ASL为n。分块（索引）查找的时间复杂度为O（m+n）。
三.二分查找
经常考的是二分查找的比较次数，或者是查找不成功需要比较的次数等。
查找不成功的比较次数为二叉判定树的最大深度，为（log2n）+1。
二分查找的ASL的计算需要画判定树。举个例子：
这里的不成功的节点是空的外部结点，注意距离不包含这些外部节点，这些只是用来计算个数的。
斐波那契查找的要求是数组个数是F【k】-1，注意不是F【K】。
三.数表查找
二叉查找树的最差情况是o（n）。
四.哈希查找
查找复杂度为O（1）
主要处理两个问题，用给定的哈希函数构造哈希表；根据选择的冲突处理方法解决地址冲突。
