C++ 查找算法

zltzlt

查找算法

查找是在大量的信息中寻找一个特定的元素。

查找算法正式定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

顺序查找算法

顺序查找也称为线形查找，属于无序查找算法。

基本思想

从数据线性结构表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值 k 相比较，若相等则表示查找成功。

若扫描结束仍没有找到关键字为 k 的节点，表示查找失败。

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表（即数组）。

顺序查找算法举例

顺序找数

输入不重复的 n 个数（n < 1000），找一个指定的数 k。

输入为两行。第一行为数 n 和 k，表示数的个数和指定的数；第二行为 n 个数，以空格隔开。

输出为一行，表示数 k 在 n 个数中的位置；如果没有，则输出 "NO"。

我的程序如下：

// 顺序找数问题

#include <iostream>
using namespace std;

int main()
{
    int a[1000], n, k, i;
    cin >> n >> k;
    for (i = 0; i < n; i++)
        cin >> a[i];
    for (i = 0; i < n; i++)
    {
        if (a[i] == k)
        {
            cout << i;
            return 0;
        }
    }
    cout << "NO";
    return 0;
}

二分查找算法

二分查找也称为折半查找，属于有序查找算法。

基本思想

用给定值 k 先与中间节点的关键字比较，中间结点把线性表分成两个子表，若相等则表示查找成功。

若不相等，再根据 k 与该中间结点的关键字比较结果确定下一步查找那个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的节点。

说明：元素必须是有序的，如果是无序的则要先进行排序操作。

二分查找举例

二分找数

输入排好序的不重复的 n 个数，找一个指定的数 k。

输入为两行，第一行为数 n 和 k，表示数的个数和指定的数；第二行为 n 个数，以空格隔开。

输出位一行，表示数 k 在 n 个数中的位置；如果没有，则输出 "NO"。

我的程序如下：

// 利用二分查找算法找数

#include <iostream>
using namespace std;

int main()
{
    int a[1000], n, k, i, mid, flag = 0, low = 1, high;
    cin >> n >> k;
    high = n;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (i = 0; i < n; i++)
    {
        if (a[i] == k)
        {
            flag = 1;
            break;
        }
    }
    if (!flag)
    {
        cout << "NO";
        return 0;
    }
    mid = (1 + n) / 2;
    while (true)
    {
        if (a[mid] > k)
        {
            high = mid - 1;
            mid /= 2;
        }
        else if (a[mid] < k)
        {
            low = mid + 1;
            mid = high - mid;
        }
        else
        {
            cout << mid;
            return 0;
        }
    }
}

递归实现二分查找：

// 递归二分查找

#include <iostream>
using namespace std;

void fun(int *a, int lo, int hi, int k)
{
    if (lo > hi)
    {
        cout << "NO";
        return;
    }
    int mi = (lo + hi) / 2;
    if (a[mi] == k)
    {
        cout << mi;
        return;
    }
    else if (a[mi] > k)
        fun(a, lo, mi - 1, k);
    else
        fun(a, mi + 1, hi, k);
}

int main()
{
    int a[1000] = {}, n, k, i, flag = 0, low = 1, high;
    cin >> n >> k;
    high = n;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    fun(a, low, high, k);
    return 0;
}

查找算法总结

查找算法有很多，这里只介绍了顺序查找和二分查找。

顺序查找就是一个一个排查。

二分查找就是一半一半排查，但是需要保证查找的是一个有序线性表。

二分查找的效率比顺序查找要高，但是其要求比顺序查找要高。

查找算法和枚举算法的相似和区别之处：

查找算法和枚举算法本质上都是搜索算法，二者是一个思路的东西。

但是枚举算法比较原始，要一个一个地去尝试。

查找算法更广泛，包括一些不是求出所有解的尝试。

枚举算法是全范围找解，不一定是找到解就结束。

查找算法是范围内找解，找到了解就可以结束。