顺序表查找

当查找的量很大时,顺序表查找的效率低。时间复杂度为O(n)

/*a为数组、key为需要查找的关键字*/
int Sequence_Search(int *a,int n,int key) {
    int i;
    for(i=0;i<n;i++) {
        if(a[i] == key) 
            return i;
    }
    return 0;
}

顺序表查找的优化

加个哨兵、取消i<n的判断

/*设置哨兵在数组开头,如果放回0 则表示查找失败*/
int Sequence_Search2(int *a;int n,int key) {
    int i;
    a[0] = key;
    i = n;
    while(a[i] != key)
        i--;
    return i;
}

折半查找(二分查找)

有序的线性表,利用加法和除法运算

每次查找都对比数组的中间值,时间复杂度O(log2n)

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

插值查找(折半查找的升级版)

有序的线性表.折半查找每次都是从固定的中间开始,插值查找可以根据查找的值key渐进查找.利用四则运算

将(high+low)/2 = low + 1/2(high-low) 中的1/2改进为 (key-a[low])/(a[high]-a[low])

斐波那契查找

利用黄金分割原理实现.利用加减法运算
一个有序表的元素个数为n,并且n正好是(某个斐波那契数 - 1),即n=F[k]-1时,才能用斐波那契查找法,如果n!=F[k]-1,这时必须要将有序表的元素扩展到大于n的那个斐波那契数 - 1才行。(如果n=10--位于f(6)/8~f(7)/13之间,此时数组要扩充至f(7)-1即12位)

对于二分查找,分割是从mid= (low+high)/2开始;而对于斐波那契查找,分割是从mid = low + F[k-1] - 1开始的; 通过上面知道了,数组a现在的元素个数为F[k]-1个,即数组长为F[k]-1,mid把数组分成了左右两部分, 左边的长度为:F[k-1] - 1, 那么右边的长度就为(数组长-左边的长度-1), 即:(F[k]-1) - (F[k-1] - 1) = F[k] - F[k-1] - 1 = F[k-2] - 1。

//斐波那契是一种极为古老的数学方法,它涉及一组奇异的数列1、1、2、3、5、8、13、21、34、55、89、144、233……
//该数列具有神奇的特性:任一数字都是由前面两个数字之和构成,前一数字与后一数字之比趋近于以固定常数0.618。
//因此,61.8%就成为了斐波那契的关键比率,也被称作“黄金比例”。
int Fibonacci_Search(int *a,int n,int key) {
    int low,high,mid,i,k;
    low = 1;
    high = n;
    k = 0;
    while(n > F[k] -1) /*数组长度到需要F[k]-1*/
        k++;

    for(i=n;i<F[K]-1;i++)   /*数组长度填充到F[k]-1--使用mid分割方便*/
        a[i] = a[n];

    while(low < high) {  
        mid = low + F[k-1]-1;
        if(key<a[min]){  /*key在左边*/
            high = mid -1;
            k = k-1;
        }
        else if(key > a[min]) {  /*key在右边*/
            low = mid +1;
            k = k-2;
        } 
        else {     /*若key与mid相等,则返回mid*/
            if(mid<=n)  
                return mid;
            else    /*mid > n--key为补全数据a[n]*/
                return n;
        }
    }
    return 0;
}

Ref:
http://blog.csdn.net/s634772208/article/details/45587179