[TOC]

术语

• 查找表（Search Table）：指由同一类型的数据元素（或记录）构成的集合。

• 关键字（Key）：是数据元素中某个数据项的值，又称为 键值，用它可以标识一个数据元素（或记录的某个字段）。
  若此关键字可以唯一地标识一个记录，则称为 主关键字（Primary Key）。
  若此关键字可以识别多个数据元素（或记录），则称为 次关键字（Secondary Key）。

• 静态查找表（Static Search Table）：只作查找操作的查找表。

• 动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。
  简单来说，动态查找表的操作就是在查找时插入数据元素或查找时删除数据元素。

• 从逻辑上来说，数据元素存储于一个集合中，集合中的记录之间并没有本质的关系。如果想从这些散列的记录之间查找所需元素，采用适当的数据结构来组合这些数据，会大幅提升查找性能。
  例如，对于静态查找表来说，可以使用线性表结构来组织数据，这样就可以使用顺序查找算法，如果再对主关键字进行排序，则可以使用更高效的折半查找算法···
  如果需要动态查找，可以考虑使用二叉排序树等查找技术。

7大查找算法

1. 顺序查找：故名思议，就是对线性表（数组或链表）依其顺序逐个进行查找。

   基本思想：顺序查找也称为线性查找，属于无序查找算法。从线性表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值 k 相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于 k 的结点，表示查找失败。

   其具体代码如下所示：

   template<typename T>
   int sequentialSearch(const T arr[], int length, T key) {
       if (arr == nullptr) {
           return -1;
       }
       for (int i = 0; i < length; ++i) {
           if (arr[i] == key) {
               return i;
           }
       }
       return -1;
   }
   

   复杂度分析：顺序查找其时间复杂度为 。

2. 折半查找（Binary Search）：又称为 二分查找。其要求进行查找的集合是有序的，且集合采用顺序存储（即数组）。
   折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直至查找成功，或查找区域无记录，查找失败。

   二分搜索具体代码如下所示：

   template<typename T>
   int binarySearch(const T arr[], int length, T key) {
       if (arr == nullptr) {
           return -1;
       }
       int low = 0,
               mid = 0,
               high = length - 1;
   
       while (low <= high) {
           mid = low + ((high - low) >> 1);
           if (key > arr[mid]) {
               low = mid + 1;
           }
           else if (key < arr[mid]) {
               high = mid - 1;
           }
           else {
               return mid;
           }
       }
       return -1;
   }
   

   复杂度分析：二分搜索的时间复杂度为

3. 插值查找（Interpolation Search）：根据要查找的关键字 key 与查找表中的最大最小记录的关键字比较后的查找方法，其核心在于插值计算公式：。

   注：插值查找 与 二分查找 的时间复杂度都是 ，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比二分查找要好的多（因为，二分查找是折半查找，而插值查找会根据要查找的 key 计算得出其在整个查找表中的权重，得到的位置会更接近 key 的位置）。反之，数组中如果分布类似 这种极端不均匀的数据，用插值查找未必是很合适的选择。

   插值查找的具体代码如下所示：

   template<typename T>
   int interpolationSearch(const T arr[], int length, const T key) {
       if (arr == nullptr) {
           return -1;
       }
       int low = 0,
               mid = 0,
               high = length - 1;
   
       while (low <= high) {
           mid = low + ((key - arr[low]) / (arr[high] - arr[low]))*(high - low);
           if (key < arr[mid]) {
               high = mid - 1;
           }
           else if (key > arr[mid]) {
               low = mid + 1;
           }
           else {
               return mid;
           }
       }
       return -1;
   }
   

4. 斐波那契查找（Fibonacci Search）：斐波那契查找与二分查找和插值查找都是有序查找算法，不过其是利用了黄金分割原理来寻找 位置。可以简单认为 斐波那契查找 就是仅使用加减实现的二分查找。

   斐波那契查找原理：对一个元素个数为 的有序序列，为了让其具备黄金分割比例，则首先在斐波那契数列中查找一个略大于该序列长度 的数 （即：），然后扩展该序列至长度为 （扩容的元素设置为原始序列的最后一个元素值）。最后进行斐波那契分割即可，即将扩展序列分割为 和 两个子序列，然后由中值 （即黄金分割点）的数值与给定查找数值进行比较，得到具体查找子序列，在该区间递归直至找到给定数值。

   注：之所以要把新序列扩容长度设为 个，是因为每次取中值 时，会占用一个元素，则新序列剩余元素为： 个，所以剩余元素就可分为 和 两个子序列，可以看到子序列与原始序列具备一样的格式，因此可以进行递归调用，程序书写会更方便简洁。而如果把新序列扩容为 个元素，则每次取中值后，还剩 个元素，则其子序列可能为： 和 或者 和 ，则程序书写就要逐个分析这些情况，会比较繁琐。

   斐波那契查找

   斐波那契查找核心算法：

   • 扩展原始序列，构造具备黄金比例新序列：

   ...
   T F[] = {0,1,1, 2,3,5,8,13,21,34,55,89…….}; // 构建斐波那契序列
   int k = 0; 
   while(n > F[k] - 1)  // 找到原始序列长度 n 位于斐波那契数列的位置
       ++k;
   T newArr[] = new T[F[k]-1]; // 构造新序列
   memcpy(newArr,arr,n*sizeof(T));  // 拷贝原始序列
   for(int i=n;i<F[k]-1;++i){
       newArr[i] = arr[n-1];  // 扩展元素值设为原始元素最后一个值
   }
   ...
   delete [] newArr;
   

   • 构造 值：mid = low + F[k-1] - 1，并进行查找：
     1）当 时，查找成功；
     2）当 时，新范围是第 low 个到第 mid-1 个，此时范围个数为 个，；
     3）当 时，新范围是第 m+1 个到第 high 个，此时范围个数为 个，。

   完整代码如下：

    #include <stdexpect>
   // 构造斐波那契序列
   void makeFibonacci(int *F, int maxSize = 50)  {
       if (F == nullptr)
           throw std::exception("F must not be null");
       F[0] = 0;
       F[1] = 1;
       for (int i = 2; i < maxSize; ++i) {
           F[i] = F[i - 1] + F[i - 2];
       }
   }
   
   template<typename T>
   int  fibonaccaSearch(const T arr[], const int length, const T key) {
       if (arr == nullptr) {
           return -1;
       }
       // 构造斐波那契序列
       int F[20] = { 0 };
       makeFibonacci(F, sizeof(F)/sizeof(int));
   
       int k = 0;
       while (length > F[k] - 1) { // 找到合适的斐波那契位置
           ++k;
       }
   
       //构造新序列
       T *newArr = new T[F[k] - 1];
       // 拷贝原始序列
       memcpy(newArr, arr, length * sizeof(T));
       for (int i = length; i < F[k] - 1; ++i) {
           newArr[i] = arr[length - 1];  // 多余元素设置为原始序列最后一个元素值
       }
   
       int low = 0,
           mid = 0,
           high = length - 1;
       while (low <= high) {
           mid = low + F[k - 1] - 1;
           if (key < newArr[mid]) {
               high = mid - 1;
               k -= 1;
           }
           else if (key > newArr[mid]) {
               low = mid + 1;
               k -= 2;
           }
           else {
               delete[] newArr;
               return mid < length ? mid : length - 1;
           }
       }
       delete[] newArr;
       return -1;
   }
   

   注：尽管斐波那契查找的时间复杂度也为 ，但就平均性能来说，斐波那契查找要优于二分查找。还有一点比较关键的地方，二分查找是进行加减法与除法运算：mid=low+(high-low)/2，插值查找进行复杂的四则运算：mid=low+(high-low)*(key-a[low])/(a[high]-a[low])，而斐波那契查找只是最简单的加减法运算：mid=low+F[k-1]-1。在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。

5. 树表查找：以树（一般为二叉树）作为数据结构存储数据元素，使用广度优先或深度优先算法进行数据查找。树表查找的实现方式有如下几种：

   • 二叉查找树：简单来讲，二叉查找树是一棵二叉树，且其左子树数值 < 根结点数值 < 右子树数值。更多详细内容，请参考：数据结构 - 树

   对于线性表来说，如果使用顺序存储结构（即数组），如果其是有序的，则在进行查找（二分，插值，斐波那契查找算法）时效率很高，但因为有序，在插入和删除操作上，就需要耗费大量的时间；而对于链式存储结构来说，其在插入和删除操作上效率很高，但在查找时效率却很低。而二叉查找树的出现，使得无论是在数据查找，还是在数据插入或删除上，都具备十分高效的性能（可以把二叉查找树看成是一个已排序的链式结构，由于已排序，因此其查找效率很高；由于是链式结构，因此其插入删除操作效率很高）。

   注：构造一棵二叉查找树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。

   二叉查找树 - 查找，具体代码如下：

   template<typename T>
   struct BiTreeNode {
       T data;
       struct BiTreeNode *pLeftChild, *pRightChild;
       BiTreeNode(const T &data) :
           data(data), pLeftChild(nullptr), pRightChild(nullptr) {}
   };
   
   template<typename T>
   BiTreeNode<T> *searchBST(BiTreeNode<T> *pHead, const T data) {
       if (pHead == nullptr) {
           return nullptr;
       }
   
       if (data < pHead->data) {
           return searchBST(pHead->pLeftChild, data);
       }
       else if (data > pHead->data) {
           return searchBST(pHead->pRightChild, data);
       }
       return pHead;
   }
   

   二叉查找树 - 插入，具体代码如下：

   template<typename T>
   void insertBST(BiTreeNode<T> *&pHead, const T data) {
       if (pHead == nullptr) {
           pHead = new BiTreeNode<T>(data);
           return;
       }
       if (data > pHead->data) {
           return insertBST(pHead->pRightChild, data);
       }
       else if (data < pHead->data) {
           return insertBST(pHead->pLeftChild, data);
       }
   }
   

   二叉查找树 - 删除：
   对于二叉查找树的删除来说，其有如下几种情况：

   • 删除的结点为叶子结点：只需直接将该结点进行删除即可；
   • 删除的结点仅有左子树或仅有右子树：只需将该结点的左子树或右子树替换为该结点即可；
   • 删除的结点既有左子树，又有右子树：这种情况相对复杂一点，以下图示例：

   假设我们先要删除 47 结点，那么它的左/右子树及其子孙结点应当做如何处理呢？

   直观的想法是把其当做只拥有左子树（或右子树）的结点，这样直接拼接该子树即可，然后将另一子树的所有结点进行插入操作。这种做法是可行的，并且简单。但是效率低下，且极大可能会让二叉树结构发生很大的变化（比如增加树的高度），因此我们不予采用。

   一个更好的想法是在删除结点的子树结点中，寻找一个结点替换该结点即可。因为二叉搜索树是有序的，因此我们对上面示例树做中序排序，结果为：，我们发现，使用结点37或者结点48替换删除结点47都可以很高效地完成删除操作。

   比如，使用结点37替换删除结点47，结果如下图所示：

   前缀替换

   比如，使用结点48替换删除结点47，结果如下图所示：

   后缀替换

   因此，对于拥有左/右子树的删除结点来说，比较好的办法就是找到删除结点的直接前驱（或直接后缀），用直接前驱（后缀）来替换该删除结点，最后删除该直接前驱（后缀）结点即可。

   具体代码如下：

   template<typename T>
   bool remove(BiTreeNode<T> *pDelete, BiTreeNode<T> *pPrev) {
       if (pDelete == nullptr) {
           return false;
       }
       BiTreeNode<T> *p = nullptr;
       if (pDelete->pRightChild == nullptr) {
           p = pDelete->pLeftChild;
           if (p) {
               pDelete->data = p->data;
               pDelete->pLeftChild = p->pLeftChild;
               pDelete->pRightChild = p->pRightChild;
           }
           else {
               p = pDelete;
               if (pPrev->pLeftChild == pDelete) {
                   pPrev->pLeftChild = nullptr;
               }
               else if (pPrev->pRightChild == pDelete) {
                   pPrev->pRightChild = nullptr;
               }
           }
       }
       else if (pDelete->pLeftChild == nullptr) {
           p = pDelete->pRightChild;
           if (p) {
               pDelete->data = p->data;
               pDelete->pLeftChild = p->pLeftChild;
               pDelete->pRightChild = p->pRightChild;
           }
           else {
               p = pDelete;
               if (pPrev->pLeftChild == pDelete) {
                   pPrev->pLeftChild = nullptr;
               }
               else if (pPrev->pRightChild == pDelete) {
                   pPrev->pRightChild = nullptr;
               }
           }
       }
       else {
           BiTreeNode<T> *pFront = pDelete;
           BiTreeNode<T> *pRight = pDelete->pLeftChild;
           while (pRight->pRightChild) {
               pFront = pRight;
               pRight = pRight->pRightChild;
           }
           pDelete->data = pRight->data;
           if (pFront != pDelete) {
               pFront->pRightChild = pRight->pLeftChild;
           }
           else {
               pFront->pLeftChild = pRight->pLeftChild;
           }
           p = pRight;
       }
       delete p;
       return true;
   }
   
   template<typename T>
   bool removeBST(BiTreeNode<T> *pHead, const T data, BiTreeNode<T> *pPrev = nullptr) {
       if (pHead == nullptr) {
           return false;
       }
       if (data > pHead->data) {
           return removeBST(pHead->pRightChild, data, pHead);
       }
       if (data < pHead->data) {
           return removeBST(pHead->pLeftChild, data, pHead);
       }
       return remove(pHead, pPrev);
   }
   

   二叉查找树 的数据元素的插入和查找的时间复杂度为 ，但最坏的情况下，比如左/右斜树，其时间复杂度为 。为了达到更好的性能，通常使用树的其他结构，比如：平衡二叉树，红黑树，B树，B+树，B*树，字典树 等等，更多内容，请参考：数据结构 - 树

6. 分块查找：又称为 索引顺序查找，是对顺序查找算法的一种改进方法。

   算法思想：将 个数据元素“按块有序”分为 块（）。每一个块中的结点不必有序，但块与块之间必须“按块有序”：即第 1 块中任一元素的关键字都必须小于第 2 块中任一元素的关键字；而第 2 块中任一元素又都必须小于第 3 块中的任一元素，……

   算法流程：

   1. 先选取各块中的最大关键字构成一个索引表；
   2. 查找元素时，分为两步：
      （1） 块间查找：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；
      （2）块内查找：定位数据所在块后，在已确定的块中用顺序法进行查找。

7. 哈希查找：根据要查找的键，在哈希表中找到对应的值。

   • 哈希表：哈希表就是一种以 键-值 存储数据的结构，我们只要输入所需查找的关键字，就可以得到对应的值。

   • 哈希函数（Hash）：也称为 散列函数，是在记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字对应一个存储位置。

   采用散列技术将记录存储在一块连续的存储空间中，我们将这块连续存储空间称为 散列表 或 哈希表（Hash table）。

   算法流程：

   1. 在存储记录时，通过散列函数计算记录的散列地址，并按该散列地址存储该记录。
   2. 在查找记录时，通过同样的散列函数就是记录的散列地址，按此散列地址访问该记录。

   复杂度分析：哈希查找 是典型的空间换时间算法策略，因此其查找性能十分高效，在没有哈希冲突的情况下，其查找时间复杂度为。

   更多详细内容，请查看：数据结构 - 哈希表