线性查找算法 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 索引查找 装饰者模式