C/C++『查找算法』

---

1 顺序表查找

1.1 常规顺序表查找

//顺序查找算法，a为数组，n为要查找的数组个数/数组下标最大值，key为要查找的关键字
int Sequential_Search(int *a, int n, int key)
{
    int i;
    for (i = 1; i <= n; i++)
    {
        if (key == a[i])
            return i;
    }
    return 0;
}

1.2 顺序表查找的优化

//顺序查找算法改进，a 为数组，n 为要查找的数组个数/数组下标最大值，key 为要查找的关键字
int Sequential_Search_Improve(int *a, int n, int key)
{
    int i;
    i = n;      //设置搜索范围从数组结尾开始
    a[0] = key; //设置a[0]为key，即设置哨兵（此时在a中一定有key值，如果返回下标为0，表示查询失败；如果返回下标非0，表示查询到key所在的位置）
    while (a[i] != key)
    {
        i--;
    }
    return i; //返回0则表示查找失败
}

---

2 有序表查找

2.1 折半查找/二分查找

//折半查找，又叫二分查找,a 为数组，n 为要查找的数组个数/数组下标最大值，key 为要查找的关键字
int Binary_Search(int *a, int n, int key)
{
    int low, mid, high;
    low = 1;  //定义最低下标为记录首位
    high = n; //定义最高下标为记录末位
    while (low <= high)
    {
        mid = (low + high) / 2; //折半
        if (key < a[mid])       //若查找值比中值小，则最高下标调整到 mid - 1 位
        {
            high = mid - 1;
        }
        else if (key > a[mid]) //若查找值比中值大，则最低下标调整到 mid + 1 位
        {
            low = mid + 1;
        }
        else //若相等，则说明mid为key所查找的位置
        {
            return mid;
        }
    }
    return 0;
}

2.2 插值查找

//插值查找,a 为数组，n 为要查找的数组个数/数组下标最大值，key 为要查找的关键字
int Interporlation_Search(int *a, int n, int key)
{
    int low, mid, high;
    low = 1;  //定义最低下标为记录首位
    high = n; //定义最高下标为记录末位
    while (low <= high)
    {
        mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); //插值
        if (key < a[mid])                                               //若查找值比中值小，则最高下标调整到 mid - 1 位
        {
            high = mid - 1;
        }
        else if (key > a[mid]) //若查找值比中值大，则最低下标调整到 mid + 1 位
        {
            low = mid + 1;
        }
        else //若相等，则说明mid为key所查找的位置
        {
            return mid;
        }
    }
    return 0;
}

2.3 斐波拉契查找

//斐波拉契查找,a 为数组，n 为要查找的数组个数/数组下标最大值，key 为要查找的关键字

//首先定义个斐波拉契分割函数
int Fibonacci(int i)
{
    if (i < 2)
    {
        return i == 0 ? 0 : 1;
    }
    return Fibonacci(i - 1) + Fibonacci(i - 2);
}

//然后定义斐波拉契搜索法
int Fibonacci_Search(int *a, int n, int key)
{
    int low, high, mid, i, k;
    low = 1;  //定义最低下标为记录首位
    high = n; //定义最高下标为记录末位
    k = 0;
    while (n > Fibonacci(k) - 1) //计算n位于斐波拉契数列的位置
    {
        k++;
    }
    for (i = n; i < Fibonacci(k) - 1; i++) //将不满的数值补满
    {
        a[i] = a[n];
    }
    while (low <= high)
    {
        mid = low + Fibonacci(k - 1) - 1; //计算当前分隔的下标
        if (key < a[mid])                 //若查找记录小于当前分隔记录
        {
            high = mid - 1; //最高下标调整到 mid - 1 位
            k = k - 1;      //斐波拉契数列下标减一位
        }
        else if (key > a[mid]) //若查找记录大于当前分隔记录
        {
            low = mid + 1; //最低下标调整到 mid + 1 位
            k = k - 2;     //斐波拉契数列下标减两位
        }
        else
        {
            if (mid <= n)
            {
                return mid; //若相等则说明 mid 即为查找到的位置
            }
            else
            {
                return n; //若 mid > n 则说明是补全数值，返回n
            }
        }
    }
    return 0;
}

---

3 线性索引查找

---

4 ……