- 顺序查找算法
- 折半查找算法
- 插值查找算法
- 斐波那契查找
顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是：从表中的第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。
代码：
int Sequential_Search(int*a,int n,int key)
{
int i;
for(i=1;i<=n;i++)
{
if(a[i]==key)
return i;
}
return 0;
}
代码优化：
int Sequential_Searchval(int*a,int n,int key)
{
int i;
a[0]=key;
i=n;
while(a[i]!=key)
{
i--;
}
return i;
}
复杂度分析：
查找成功时的平均查找长度为：（假设每个数据元素的概率相等）
ASL = (1+2+3+…+n)/n = (n+1)/2 ;
当查找不成功时，需要n+1次比较，时间复杂度为O(n);
所以，顺序查找的时间复杂度为O(n)。
折半查找，又称二分查找，核心是，通过不断缩小筛选的范围，来实现对key的查找。
以升序数列为例，比较一个元素与数列中的中间位置的元素的大小，如果比中间位置的元素大，则继续在后半部分的数列中进行查找；如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数列长度都会是之前数列的一半，直到找到相等元素的位置或者最终没有找到要找的元素。
这就是简单的二分查找思想
时间复杂度：
O(logn)
代码实现
int Binary_Search(int*a,int n,int key)
{
int low,high,mid;
low=1;
high=n;
while(low<=high)
{
mid=(low+high)/2;
if(a[mid]>key)
{
high=mid-1;
}
else if(a[mid]
插值查找算法
在前面的二分查找中，mid=(1/2)*(low+high)
这个式子可以化为 mid=(low+high)/2=low+(1/2)*(high-low)
现在，我们对（high-low）前面的系数进行改进
改为 (key-a[low])/(a[high]-a[low])，为什么呢，认真思考你会发现，这样计算会使mid的值更接近目标值key的下标，这样就可在二分查找算法的基础上进一步优化查找过程
插值查找是根据要查找的关键字Key与查找表中最大最小记录的关键字比较后的查找方法，其核心是差值计算公式(key-a[low])/(a[high]-a[low])
代码实现：
int Interpolation_Search(int*a,int n,int key)
{
int low,high,mid;
low=1;
high=n;
while(low<=high)
{
mid=low+(key-a[low])/(a[high]-a[low])*(high-low);
if(key>a[mid])
{
low=mid+1;
}
else if(key
时间复杂度：
O(logn)
斐波那契查找
实现前提：有一组斐波那契数组
斐波那契查找原理：与前两种相似，仅仅改变了中间节点（mid）的位置，mid不再是中间或插值得到的
而是位于黄金分割点附近，即mid=low+F(k-1)-1
推导：
由斐波那契数列的性质得 F[k]=F[k-1]+F[k-2]，然后进一步推到可以得到，
(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1;
上面式子很好推导
再结合下面的图，可以推出 mid=low+F(k-1)-1时，mid就处于黄金分割点
但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1,这里的k只要能使
F[k]-1恰好大于或等于n即可。
即：
while(n>F[k]-1)
k++;
代码实现：
int Fib_Search(int*a,int n,int key)
{
int low,high,mid,i,k;
low=1;
high=n;
k=0;
while(n>F[k]-1)
k++;
for(i=n;ia[mid]) //在数组后面找
{
low=mid+1;
k=k-2;
//1.全部元素 = 前面元素 + 后面元素
//2.F[k] = F[k-1] + F[k-2]
//3.后面元素有F[k-2]个,F[k-2]=F[k-3] + F[k-4]
//即在F[k-2]后面继续查找
//所以k=k-2
}
else
{
if(mid<=n)
return mid;
else
return n;
}
}
return 0;
}
时间复杂度：
O(logn)
