参考教材：《算法设计与应用》 汪荣贵 杨娟 薛丽霞 机械工业出版社

第7章 查找算法设计与分析

查找，顾名思义，是指在大量的数据元素中通过一定的方法寻找某个特定的元素。
以查找策略为标准，可分为二分查找、斐波那契查找、索引表查找、哈希表查找、广度深度优先查找、红黑树查找、B树查找等。
以查找形式为标准，可将排序算法分为如下4种基本类型，即静态表查找算法、散列表查找算法、搜索树查找算法和特殊树查找算法。

7.1 静态表查找算法

静态查找表就是使用静态的表结构进行查找，在查找的过程中表结构始终保持不变。

7.1.1 顺序表查找

  1. // 顺序表查找算法
  2. // 输入：数组A，数组元素个数n，待比较关键字的值K
  3. // 输出：查找的结果
  5. #include <iostream>
  7. using namespace std;
  9. int Sequece_Search(int A[], int n, int K) {
  10.     for (int i = 0; i < n; i++) {
  11.         if (A[i] == K) return i;
  12.     }
  13.     return -1;
  14. }
  16. int main() {
  17.     int A[] = { 1,2,3,4,5 };
  18.     int res = Sequece_Search(A, 5, 3);
  19.     cout << res;
  20.     return 0;
  21. }

7.1.2 有序表查找

对于以数组方式存储的数据，如果已按其关键字值的大小顺序排好，则称为有序数组或有序表

1、折半查找

  1. // 折半查找算法
  3. #include <iostream>
  5. using namespace std;
  7. int bin_search(int a[], int low, int high, int key) {
  8.     if (low > high)
  9.         return -1;
  10.     else {
  11.         int mid = (low + high) / 2;
  12.         if (a[mid] == key) return mid;
  13.         else if (key < a[mid]) {
  14.             return bin_search(a, low, mid - 1, key);
  15.         }
  16.         else {
  17.             return bin_search(a, mid + 1, high, key);
  18.         }
  19.     }
  20. }
  22. int main() {
  23.     int A[] = { 1,2,3,4,5 };
  24.     int res = bin_search(A, 0, 5, 3);
  25.     cout << res;
  26.     return 0;
  27. }

3、斐波那契查找

通过斐波那契数列来构造类似于堆查找

  1. // 斐波那契查找算法
  2. // 输入：数组a，数组长度，待查找关键字key
  3. // 输出：返回查找结果，若查找成功，返回key在数组中的下标，否则返回-1
  5. #define MAXSIZE 13
  7. #include <iostream>
  9. using namespace std;
  11. // 非递归算法构造斐波那契数列
  12. void Fibonacci(int* f) {
  13.     f[0] = 0;
  14.     f[1] = 1;
  15.     for (int i = 2; i < MAXSIZE; i++) {
  16.         f[i] = f[i - 1] + f[i - 2];
  17.     }
  18. }
  20. int Fibonacci_Search(int* a, int n, int key) {
  21.     int low, high, mid;
  22.     low = 0;
  23.     high = n - 1;
  24.     int k = 0;
  25.     int F[MAXSIZE];
  26.     Fibonacci(F);
  27.     //查找n在斐波那契数列中的位置
  28.     while (n > F[k] - 1) {
  29.         k++;
  30.     }
  31.     //查找n在斐波那契数列中的位置
  32.     while (n > F[k] - 1) {
  33.         k++;
  34.     }
  35.     //将a的元素扩展到“某斐波那契数-1”.即F[k]-1
  36.     for (int i = n; i < F[k] - 1; i++) {
  37.         a[i] = a[high];
  38.     }
  39.     //当键值小于a[mid]时，就在[low,F[k-1]-1]范围内查找；当键值大于a[mid]时，就在[F[k-2]-1,high]范围内查找
  40.     while (low <= high&&k>=1) {
  41.         mid = low + F[k - 1] - 1;
  42.         if (key < a[mid]) {
  43.             high = mid - 1;
  44.             k = k - 1;
  45.         }
  46.         else if (key > a[mid]) {
  47.             low = mid + 1;
  48.             k = k - 2;
  49.         }
  50.         else {
  51.             if (mid <= high) {
  52.                 //mid即为查找到的位置
  53.                 return mid;
  54.             }
  55.             else {
  56.                 //扩展的数组，返回n-1
  57.                 return n - 1;
  58.             }
  59.         }
  60.     }
  61.     return -1;
  62. }
  64. int main() {
  65.     int A[] = { 1,3,5,7,10,11,15,18,19,22,24,25 };
  66.     int res = Fibonacci_Search(A, 12, 1);
  67.     cout << res;
  68.     return 0;
  69. }

7.1.3 静态树表查找

静态树表将有序表中数据元素按照被查找概论的不同生成一棵二叉树，概率最大的数据放在根的位置或者放在离根较近的位置，同时也使得从二叉树的根结点起，查找左右子树的概率大致相等，使平均查找长度较短。
image.png
image.png