静态查找表
：
只进行查找操作的查找表
动态查找表：
在查找过程中同时插入查找表中不存在的元素，或者删除已存在的元素
本文主要总结静态查找表
1.顺序表查找：
从第一个或者最后一个记录开始，将每个记录的关键字与给定值比较，若相等则查找成功。
C++实现：
for(int i=0;i<n;i++)
{
if(a[i]==key)
return i;
}
return 0;
时间复杂度：
最好情况：O(1)，第一次就找到
最坏情况：O(n)，需要逐个比较完
平均：O(n)
2.有序表查找：
元素是有序排列的，且是顺序存储的（存在数组或者vector）。主要包括二分查找，插值查找，斐波拉契查找
2.1二分查找（折半查找）
基本思想：
（1）与中间元素比较，其中mid=low+1/2*(low+high)
（2）等于中间元素，则查找成功
（3）大于中间元素，在它的右半区查找，重复（1）；小于中间元素，在它的左半区查找，重复（1），直到找到给定值。
C++实现：
//n是有序表长度
int low=0,high=n-1;
while(low<high)
{
int mid=(low+high)/2;
if(key<a[mid])
high=mid-1;
else if(key>a[mid])
low=mid+1;
else
return mid;
}
return 0;
时间复杂度：
最好：O(1)
最坏：O(logn+1)
平均：O(logn)
2.2插值查找（折半查找升级版）
二分查找中：
mid=low+1/2*(low+high)
插值查找:
mid = low + (key – a[low]) / (a[high] – a[low]) * (high – low)，也就是将上述的比例参数1/2改进了，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数
因为如果在一个有序表中找相对较小的元素（即离low更近一点），就mid向low靠近一点；找相对较大的元素（即离high更近一点），就mid向high靠近一点；这样效率比较高。但要求表中元素分布比较均匀。
时间复杂度：O(logn)
2.3斐波那契查找
斐波拉契数列：0,1,1,2,3,5,8,13,21,34，F(k)
基本思想：
（1）将有序数组的数值补全，使它的长度等于某个斐波拉契数F(k)-1
（2）取low=0,mid=low+F(k-1)-1,high=F(k)-2
（3）当给定值小于a[mid]值，在mid前半段查找，且前半段长度为F(k-1)-1；当给定值大于a[mid]值，在mid后半段查找，且后半段长度为F(k-2)-1；重复（2）
时间复杂度：O(logn)
因为斐波拉契查找求mid=low+F(k-1)-1，只有加减法，没有乘法，这种细微差别相比较前两种方法要好一些。
C++实现：
int low=0,high=n-1,mid,k=0;
while(n>F(k))
k++;
for(i=n;i<F(k)-2;i++)
a[i]=a[n-1];
while(low<high)
{
mid=low+F(k-1)-1;
if(key<a[mid])
{
high=mid-1;
k=k-1;
}
else if(key>a[mid])
{
high=mid+1;
k=k-2;
}
else
{
if(mid<=n) return mid;
else return n; //是后面补的
}
return 0;
3.散列表查找（哈希表，hash table）
散列表：关键字key和存储位置之间有一个确定关系f，称为散列函数（哈希函数），要找到关键字key，只需计算f(key)就可以直接得到存储位置。连续存储。查找复杂度O(1)。
但有时候两个不同的关键字k1和k2，f(k1)=f(k2)，会产生冲突。这就尴尬了……所以尽量构造散列函数让冲突尽可能少。