数据结构与算法-数组查找

1. 顺序查找

1.1 普通顺序查找

int SequentialSearch(int *a, int n, int key) {
    for (int i = 0; i < n; i++) {
        if (a[i] == key) {
            return i;
        }
    }
    return NOT_FOUND;
}

1.2 哨兵顺序查找

我们看到，顺序查找的时候每次都要先判断，能不能去掉这个判断呢？

我们可以使用一个哨兵，即数组第0位是空出来的情况，将其作为哨兵，存入查询值。

• 引入哨兵后，肯定可以在数组中找到查询值，若在中途找到，即数组中确实有这个值；若最后才找到，说明找到的是我们的哨兵，数组中没有这个值。

注意： 使用哨兵，①第0位存储时空出来；②返回0表示没有找到。

int SequentialSearch2(int *a, int n, int key) {
    int i = n;
    a[0] = key;
    while (a[i--] != key);
    return i;
}

2. 折半查找与变体

折半查找和相关变体，需要数组是有序的！下面的算法针对升序数组进行说明。

下面几种算法都是折半和折半公式的变式，核心都是缩小范围，利用夹逼定理进行搜索。

2.1 折半查找

通过范围折半，不断缩小搜索范围，节省时间。

int BinarySearch(int *a, int n, int key) {
    int l,c,r;
    l = 0;
    r = n-1;
    while (l <= r) {
        c = (l + r) >> 1;// 折半
        if (key < a[c]) {
            r = c - 1;
        } else if (key > a[c]) {
            l = c + 1;
        } else {
            return c;
        }
    }
    return NOT_FOUND;
}

2.2 插入查找

需要每个数据的分布是一致的。通过计算查询值在整体范围的偏移量进行查询。

int InterpolationSearch(int *a, int n, int key){
    int l,c,r;
    l = 1;
    r = n-1;
    while (l <= r) {
        //插值
        c = l + (r-l)*(key-a[l])/(a[r]-a[l]);
        if (key < a[c]) {
            r = c - 1;
        } else if (key > a[c]) {
            l = c + 1;
        } else {
            return c;
        }
    }
    return NOT_FOUND;
}

2.3 斐波那契查找

通过斐波那契数列递增的特性，反过来利用，即递减特性，缩小范围。

• 注意点是数量不够的部分需要进行补齐。

int F[100]; /* 斐波那契数列 */
int Fibonacci_Search(int *a, int n, int key){
    int l, c, r;
    l = 0;
    r = n-1;
    
    int k = 0;
    //1.计算n为斐波拉契数列的位置
    while (n > F[k]) {
        k++;
    }
    //2.将数组a不满的位置补全值;
    for (int i = n; i < F[k]; i++) {
        a[i] = a[n-1];
    }
    
    while (l <= r) {
        c = l + F[k-1] - 1; //计算当前分隔的下标
        if (key < a[c]) {
            r = c-1;
            k = k-1; //斐波拉契数列下标减1位
        } else if (key > a[c]) {
            l = c+1;
            k = k-2; //斐波拉契数列下标减2位
        } else {
            return c < n ? c : n-1;
        }
    }
    return NOT_FOUND;
}