线性查找算法 gaunthan Posted on Jan 17 2017 ? Searching ? ? Algorithm ? > **查找**(Searching)就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。 ## 顺序查找 ### 思想 **顺序查找**(Sequential Search)又称为线性查找，是最基本的查找技术，其过程为：从表的一端开始，逐个进行记录的关键字和给定值的比较，直到相等或所有关键字都进行了一次比较为止。对于前者，查找成功；对于后者，查找失败。 对于顺序表和链表，顺序查找都适用。只要给定的数据结构能够满足前向迭代操作，即可使用该算法。 ### 算法实现 #### 伪代码 ```c SequentialSearch for record in records if record.key() == key return position of record return not found ``` 注意，查找算法也可以返回bool变量，表示给定关键字是否存在。但是一般来说，返回查找位置更为常见。 #### C ```c long SeqSearch(const int a[], const size_t num, const int key) { for(size_t i = 0; i != num; ++i) { if(a[i] == key) return i; } return -1; } ``` #### C++ ```cpp template<typename FwdIter, typename T > FwdIter SeqSearch(FwdIter first, FwdIter last, const T& key) { while(first != last) { if(*first == key) return first; ++first; } return last; } ``` ### 优化 如果我们可以在不增加太多操作时间的情况下，并且允许向输入的线性表附加记录，则可以使用**哨兵**来避免上面实现中的越界检测： ```c long SeqSearch(int a[], const size_t num, const int key) { size_t i = 0; a[num] = key; // 把哨兵附加到表尾 while(a[i] != key) { ++i; } return i == num ? -1 : i; } ``` ### 复杂度分析 #### 时间复杂度 对于顺序查找，由于其逐个依次地进行关键字的比较，又由于关键字在任一位置的概率相同，因此很容易得出它的平均时间复杂度，为$\theta (N)$， #### 空间复杂度 由于查找过程没有对记录进行计算，仅仅是关键字值的比较，因此空间复杂度显然是$O(1)$。 ## 折半查找 ### 思想 **折半查找**(Binary Search)的工作流程为：在**有序的顺序表**中，取中间记录作为比较对象，若给定值与该记录的关键字相同，则查找成功；若给定值大于该记录的关键字，则说明查找位置在右半区间，因此对右半区间继续折半查找；否则，对左半区间继续折半查找。 ### 算法实现 折半查找本身是递归定义的，因此使用递归来实现它能够获得很好的简洁性。 #### 递归实现 ```c #define KEY_NOT_FOUND -1 int BinSearch(const int a[], const int low, const int high, const int key) { int mid; if(!a || low < 0 || low > high) return KEY_NOT_FOUND; // 这里不用mid = (low + high) / 2，因为相加可能溢出 mid = low + (high - low)/2; if(a[mid] == key) return mid; else if(a[mid] < key) return BinSearch(a, mid + 1, high, key); else return BinSearch(a, low, mid - 1, key); } ``` #### 迭代实现 折半查找也可以非常容易地以迭代的方式实现： ```c int BinSearch(const int a[], int low, int high, const int key) { int mid; if(!a || low < 0 || low > high) return KEY_NOT_FOUND; while(low <= high) { mid = low + (high - low)/2; if(a[mid] == key) return mid; else if(a[mid] < key) low = mid + 1; else high = mid - 1; } return KEY_NOT_FOUND; } ``` 为了方便用户，可以对上面的接口进行一层封装： ```c #define BinarySearch(a, length, key) BinSearch((a), 0, (length) - 1, (key)) ``` ### 复杂度分析 #### 时间复杂度 对于折半查找，由于每次比较都能够”去掉“一半的比较记录，又由于关键字在任一位置的概率相同，因此很容易得出它的平均时间复杂度，为$\theta (logN)$， #### 空间复杂度 由于查找过程没有对记录进行计算，仅仅是关键字值的比较，因此空间复杂度显然是$O(1)$。 ## 插值查找 现在请先让我问一个问题：我们使用字典去查单词的时候，是用的折半查找吗？ 其实，我们在查单词时，显然不只是单纯的一半一半的查。我们知道关键字（单词）是按字母排序的（字典序），因此我们在查找a、b、c等排在前面的字母开头的单词时，会主动地在字典的前面部分查。而在查找z开头的单词时，会直接翻到字典的最后来找。 ### 思想 **插值查找**(Interpolation Search)是根据要查找的关键字key与顺序表中最大、最小记录的关键字比较后的查找方法，它假设输入数组是线性增加的（这个假设的精确度会影响算法的效率，但不会影响算法的正确性）。 插值查找的核心在于： 1. 除了比较下标的计算与折半查找不同，其他过程都是一样的 2. 不使用$low + {1 \over 2}(high - low)$来计算参与比较的记录的下标 3. 关键字参与该下标的计算： $$ low + { {key - a[low]} \over {a[high] - a[low]} }(high - low) $$ 对于表较长，关键字分布又比较均匀的查找表，插值查找比折半查找的平均性能要好得多。然而，如果顺序表的关键字分布极端不均匀，则使用插值查找不是很好的选择。因为它就会像[快速排序](http://leanote.com/blog/post/5783b770ab644133ed0088ce)一样，一次操作把输入给分成了极大和极小的两个集合，然后又对极大的集合进行操作。 ### 复杂度分析 #### 时间复杂度 插值查找的时间复杂度也是$O(logN)$。 #### 空间复杂度 空间复杂度为$O(1)$。 ## 斐波那契查找 折半查找是从中间分，插值查找是从接近关键字的地方分，那么还有没有其他的分法？ ### 思想 **斐波那契查找**(Fibbonacci Search)是利用黄金分割原理来实现查找子集的划分的。假设$F$是一个下标从0开始的斐波那契数列，该算法的关键步骤为： 1. 当$key = a[mid]$时，查找成功； 2. 否则，若$key < a[mid]$，则新范围是$[low, mid - 1]$，此范围有$F[k - 1] - 1$个元素； 3. 否则，因$key > a[mid]$，新范围是$[mid + 1, high]$，此范围有$F[k - 2] - 1$个元素。 注意，每递归一次，k就减1（如果在右边递归）或减2（如果在左边递归）,使得分割能够相异地进行。其他过程与折半查找大致相同。 ### 复杂度分析 #### 时间复杂度 斐波那契查找的时间复杂度也为$O(logN)$，但就平均性能而言，要优于折半查找。只是对于最坏情况，斐波那契查找的时间复杂度为$O(n)$，而折半查找的最坏时间复杂度仍是$O(logN)$。 还有比较关键的一点，折半查找是进行加法与除法运行，插值查找进行复杂的四则运算，而斐波那契查找只是最简单的加减法运算。在查找海量数据时，这一点可能成为关键因素。 ## References - 莱维汀, A.). 算法设计与分析基础(第3版)[M]. 清华大学出版社, 2015. - 程杰. 大话数据结构[M]. 清华大学出版社, 2011. 赏 Wechat Pay Alipay 索引查找 装饰者模式
