查找的概念 ​

查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。

查找的定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找算法分类：

1. 静态查找和动态查找；

   注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2. 无序查找和有序查找。

   无序查找：被查找数列有序无序均可；

   有序查找：被查找数列必须为有序数列。

平均查找长度（Average Search Length，ASL）：需和指定 key 进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于含有 n 个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci 的和。 Pi：查找表中第 i 个数据元素的概率。 Ci：找到第 i 个数据元素时已经比较过的次数。

顺序查找 ​

什么是顺序查找？ ​

顺序查找（sequential search），也称穷举查找，是一种基本的查找算法。

顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法。静态查找表既可以使用顺序表表示，也可以使用链表结构表示。虽然一个是数组、一个链表，但两者在做查找操作时，基本上都是大同小异。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

顺序查找的改进 ​

顺序查找的改进：设置一个“哨兵”，就是等待查询的值，放在查找方向的尽头处，避免了每一次比较后都要判断一下当前的位置是否越界了。

习惯上我们一般将“哨兵”放在开头，然后逆序查找，放置好“哨兵”以后，从没有“哨兵”的一端依次遍历，如果查找的数据与关键字（key 值）相等，则输出，当程序运行到“哨兵”处，查询结束。

二分法查找 ​

什么是二分法查找 ​

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。

但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找每次都能将查找区间减半，这种折半特性的算法时间复杂度都为 O(logN)。

• 时间复杂度：O(log~n~)
• 空间复杂度：O(1)

查找过程 ​

找到区间的中间值，与目标值比较，如果等于则返回；如果小于目标值则将区间缩小为右区间；反之缩小为左区间。

关键在于确定中间值与区间缩小时的边界。

确定中值 ​

有两种计算中值 m 的方式：

• m = (l + h) / 2
• m = l + (h - l) / 2

l + h 可能出现加法溢出，最好使用第二种方式。

确定边界 ​

边界也有两种常用的写法：

• 左闭右闭：[left, right]
• 左闭右开：[left, right)

当取左边界时，第一种写法的 right 应该为 right = mid-1，而第二种为 right = mid