C++ 查找算法

zltzlt

查找算法

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

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

顺序查找算法

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

基本思想

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

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

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

顺序查找算法举例

顺序找数

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

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

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

我的程序如下：

1. // 顺序找数问题
   
2. 
   
3. #include <iostream>
   
4. using namespace std;
   
5. 
   
6. int main()
   
7. {
   
8.     int a[1000], n, k, i;
   
9.     cin >> n >> k;
   
10.     for (i = 0; i < n; i++)
    
11.         cin >> a[i];
    
12.     for (i = 0; i < n; i++)
    
13.     {
    
14.         if (a[i] == k)
    
15.         {
    
16.             cout << i;
    
17.             return 0;
    
18.         }
    
19.     }
    
20.     cout << "NO";
    
21.     return 0;
    
22. }

复制代码

二分查找算法

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

基本思想

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

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

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

二分查找举例

二分找数

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

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

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

我的程序如下：

1. // 利用二分查找算法找数
   
2. 
   
3. #include <iostream>
   
4. using namespace std;
   
5. 
   
6. int main()
   
7. {
   
8.     int a[1000], n, k, i, mid, flag = 0, low = 1, high;
   
9.     cin >> n >> k;
   
10.     high = n;
    
11.     for (i = 0; i < n; i++)
    
12.     {
    
13.         cin >> a[i];
    
14.     }
    
15.     for (i = 0; i < n; i++)
    
16.     {
    
17.         if (a[i] == k)
    
18.         {
    
19.             flag = 1;
    
20.             break;
    
21.         }
    
22.     }
    
23.     if (!flag)
    
24.     {
    
25.         cout << "NO";
    
26.         return 0;
    
27.     }
    
28.     mid = (1 + n) / 2;
    
29.     while (true)
    
30.     {
    
31.         if (a[mid] > k)
    
32.         {
    
33.             high = mid - 1;
    
34.             mid /= 2;
    
35.         }
    
36.         else if (a[mid] < k)
    
37.         {
    
38.             low = mid + 1;
    
39.             mid = high - mid;
    
40.         }
    
41.         else
    
42.         {
    
43.             cout << mid;
    
44.             return 0;
    
45.         }
    
46.     }
    
47. }

复制代码

递归实现二分查找：

1. // 递归二分查找
   
2. 
   
3. #include <iostream>
   
4. using namespace std;
   
5. 
   
6. void fun(int *a, int lo, int hi, int k)
   
7. {
   
8.     if (lo > hi)
   
9.     {
   
10.         cout << "NO";
    
11.         return;
    
12.     }
    
13.     int mi = (lo + hi) / 2;
    
14.     if (a[mi] == k)
    
15.     {
    
16.         cout << mi;
    
17.         return;
    
18.     }
    
19.     else if (a[mi] > k)
    
20.         fun(a, lo, mi - 1, k);
    
21.     else
    
22.         fun(a, mi + 1, hi, k);
    
23. }
    
24. 
    
25. int main()
    
26. {
    
27.     int a[1000] = {}, n, k, i, flag = 0, low = 1, high;
    
28.     cin >> n >> k;
    
29.     high = n;
    
30.     for (i = 0; i < n; i++)
    
31.     {
    
32.         cin >> a[i];
    
33.     }
    
34.     fun(a, low, high, k);
    
35.     return 0;
    
36. }

复制代码

查找算法总结

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

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

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

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

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

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

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

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

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

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