1. 二分查找（折半查找）
它的前提是线性表中的记录必须是有序的，线性表必须采用顺序存储。折半查找的基本思想是:在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
1.1 代码实现
1.2 性能分析
其时间复杂度是O(logn),不过由于折半查找的前提是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法是比较好的。但是对于需要频繁插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，不建议使用。
2. 插值查找（按比例查找法）
对于前面的折半查找，为啥一定要折一般，而不是1/4或者其他？比如：我们查字典Apple，我们会先从中间查找，还是有一定目的的向前找。或者在0-1000个数之间有200个元素从小到大均匀分布排序，我们若是需要查找到15，我们会去中间查找500，还是直接去前面开始查找。以上都说明我们上面的折半查找可以再进行改进。
基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，插值查找也属于有序查找。
2.1 代码实现
2.2 性能分析
而插值查找则比较灵活,并不是简单的从中间进行的,它是根据我们需要查询的值的渐进进行搜索的.插值查找的不同点在于每一次并不是从中间切分,而是根据离所求值的距离进行搜索的.
对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
时间复杂度：平均情况O（loglog(n)），最坏O（log(n)）
3. 斐波那契查找
除了插值查找之外，我们再介绍一种有序查找，可以对折半进行优化，那就是斐波那契查找，利用了黄金分割原理来实现的
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1;
越向后，每两个数之间相除越接近黄金比例
网友评论