顺序表的几种查找

顺序查找

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;
}
// 有哨兵版
// 时间复杂度O(n)
int Sequential_search(int* a,int n,int key)
{
    int i;
    a[0]=key;
    i=n;
    while(a[i]!=key)
        i--;
    return i;
}

折半查找（二分查找）

二分检索算法的每一步，搜索空间总会减半，因此保证了运行时间。在数组中查找一个特定元素，可以保证在 O(log(n))时间内完成，而且如果找的正好是中间元素就更快了。也就是说，要从81,920,000个元素的数组中找某个元素的位置，只需要27个甚至更少的迭代。
由于二分检索的随机跳跃性，该算法并非缓存友好的，因此只要搜索空间小于特定值（64或者更少），一些微调的二分检索算法就会切换回线性检索继续查找。然而，这个最终的空间值是极其架构相关的，因此大部分框架都没有做这个优化。

// 时间复杂度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]<key)
            low=mid+1;
        else                        //a[mid]==key
            return mid;
    }
    return 0;
}

插值查找

类似于人类使用电话簿的方法，它试图通过假设元素在数组中均匀分布，来猜测元素的位置。
首先，它抽样选择出搜索空间的开头和结尾，然后猜测元素的位置。算法一直重复这个步骤，直到找到元素。如果猜测是准确的，比较的次数大概是O(log(log(n))，运行时间大概是O(log(n))；但如果猜测的不对，运行时间就会是O(n)了。
对于分布比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多

// 插值查找
int Insert_Search(int* a,int n,int key)
{
    int low,high,mid;
    low=1;
    high=n;
    while(low<=high)
    {
        mid=low+(high-low)*(key-a[low])/(a[high]-a[low]);            //插值
        if(a[mid]>key)
            high=mid-1;
        else if(a[mid]<key)
            low=mid+1;
        else                        //a[mid]==key
            return mid;
    }
    return 0;
}

# 斐波那契查找
在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。
波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。
斐波那契查找的时间复杂度还是O(log2n)，但是 与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。

// 斐波那契查找
// 斐波那契数列：
// 0    1     2     3     4     5     6    ....
// 0    1     1     2     3     5     8    ....
int Fibonacci_Search(int* a,int n,int key)
{
    int low,hgih,mid,i,k;
    low=1;
    high=n;
    k=0;
    while(n<F[k]-1)            //计算n位于斐波那契数列的位置
        k++;
    for(i=n;i<F[k]-1;i++)    //对不满的数值补全，防止数组越界
        a[i]=a[n];
    while(low<=high)
    {
        mid=low+F[k-1]-1;
        if(a[mid]>key)
        {
            high=mid-1;
            k=k-1;
        }
        else if(a[mid]<key)
        {
            low=mid+1;
            k=k-2;
        }
        else
        {
            if(mid<n)
                return mid;
            else
                return n;        //mid>n说明是最后一个，返回n
        }
    }
    return 0;
}

要点：
1. 当key=a[mid]时，查找成功
2. 当keya[mid]时，新范围是第mid+1个到第high个，此时范围个数为F[k-2]-1个