顺序查找的几种方式

顺序查找，又叫线性查找，是最基本的查找技术，他的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，如果全部比较仍没有相等的，则查找失败。

1. 顺序查找

//a为数组,n为查找的数组个数,key为要查找的关键字;
int Sequential_Search(int *a,int n,int key){
    for (int i = 1; i <= n ; i++)
        if (a[i] == key)
            return i;

    return 0;
}

顺序查找的优化

// 顺序查找优化
int Sequential_Search2(int *a, int n, int key){

    a[0] = key;
    int i = n; // 从后向前，减少for循环中 <= 计算

    while (a[i] != key) {
        i--;
    }
    return i;
}

2. 折半查找/二分查找

// 二分查找/折半查找
int Binary_Search(int *a, int n, int key){
    int low = 1;
    int high = n;
    int mid = 0;
    while (low <= high) {
        mid = (low + high)/2;
        if (a[mid] > key) {
            high = mid-1;
        }else if (a[mid] < key){
            low = mid+1;
        }else{
            break;
        }
    }
    return mid;
}

3. 插值查找

// 插值查找
int Interpolation_Search(int *a, int n, int key){
    int low = 1;
    int high = n;
    int mid = 0;

    while (low <= high) {
        mid = low + (key-a[low]) / (a[high]-a[low]) * (high-low);
        if (a[mid] > key) {
            high = mid-1;
        }else if (a[mid] < key){
            low = mid+1;
        }else{
            break;
        }
    }
    return mid;
}

4. 斐波拉契查找

int F[100];

int Fibonacci_Search(int *a, int n, int key){

    int low,high,mid,i,k;
    low = 1;
    high = n;
    k = 0;
    // 1.计算n为斐波拉起数列的位置
    while (n > F[k]-1) {
        k++;
    }
    // 2.将数组a不满的位置补全
    for (i = n; i<F[k]-1; i++) {
        a[i] = a[n];
    }
    //3.循环对比
    while (low <= high) {
        // 计算当前分割的下标
        mid = low + F[k-1] - 1;
        if (key < a[mid]) {
            high = mid - 1;
            k = k-1;
        }else if (key > a[mid]){
            low = mid + 1;
            k = k-2; //
        }else{
            if (mid <= n) {
                return mid;
            }else{
                return n;
            }
        }
    }
    return 0;
}

文章永久链接：https://tech.souyunku.com/31402