C语言实现七大查找算法（一）

爱被打了一巴掌 2022-02-24 07:42 1076阅读 0赞

本文主要介绍数据结构中的查找算法，主要介绍**顺序查找**、**折半查找（二分查找）**、**树表查找**、**分块查找**、**哈希查找（散列）**。 其他的一些查找算法也会有所介绍。

查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

1.  **查找表（Search Table）**：由同一类型的数据元素构成的集合
2.  **关键字（Key）**：数据元素中某个数据项的值，又称为键值
3.  **主键（Primary Key）**：可唯一的标识某个数据元素或记录的关键字

**查找表按照操作方式可分为：**

1.  \*\*静态查找表（Static Search Table）：\*\*只做查找操作的查找表。它的主要操作是：

>  *  查询某个“特定的”数据元素是否在表中
>  *  检索某个“特定的”数据元素和各种属性

1.  \*\*动态查找表（Dynamic Search Table）：\*\*在查找中同时进行插入或删除等操作：

>  *  查找时插入数据
>  *  查找时删除数据

\*\*平均查找长度（Average Search Length，ASL）：\*\*在所有的查找过程中进行关键字的比较次数的平均值。  
对于含有n个数据元素的查找表，查找成功的平均查找长度计算公式如下：  
 A S L = ∑ i = 1 n P i C i ASL = \\sum\_\{i=1\}^\{n\}P\_\{i\}C\_\{i\} ASL=i=1∑nPiCi  
　　 P i P\_i Pi：查找表中第i个数据元素的概率,一般等概率为 1 n \\frac\{1\}\{n\} n1  
　　 C i C\_i Ci：找到第i个数据元素时已经比较过的次数。

### 顺序查找 ###

**算法简介**  
顺序查找又称为线性查找，是一种最简单的查找方法。**适用于线性表的顺序存储结构和链式存储结构**。**时间复杂度为 O （ n ） O（n） O（n）**。

**基本思路**

从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。

**优缺点**

*  缺点：当n 很大时，平均查找长度较大，效率低；
 *  优点：对表中数据元素的存储没有要求。另外，**对于线性链表，只能进行顺序查找**。

**算法实现**

//顺序查找，n为数组a的长度
    int SequenceSearch(int a[], int value, int n)
    {
        
        int i;
        for(i=0; i<n; i++)
            if(a[i]==value)
                return i;
        return -1;
    }

### 折半查找 ###

**算法简介**  
折半查找，也称二分查找（Binary Search），是一种在**有序数组**中查找某一特定元素的查找算法。查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。  
这种查找算法每一次比较都使查找范围缩小一半。**时间复杂度为 O （ l o g 2 n ） O（log\_2^n） O（log2n）**。

**基本思路**  
给予一个包含 n个带值元素的数组A  
1、 令 L为0 ， R为 n-1 ；  
2、 如果L>R，则搜索以失败告终 ；  
3、 令 m (中间值元素)为 ⌊(L+R)/2⌋ **(向下取整)**；  
4、 如果  A m < T A\_m<T Am<T，令 L为 m + 1 并回到步骤二 ；  
5、 如果  A m > T A\_m>T Am>T，令 R为 m - 1 并回到步骤二；

**注意：**  
**折半查找的前提条件是需要有序表顺序存储**，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

**算法实现**

//二分查找（折半查找）,一般方法，n为数组a的长度
    int BinarySearch1(int a[], int value, int n)
    {
        
        int low, high, mid;
        low = 0;
        high = n-1;
        while(low<=high)
        {
        
            mid = (low+high)/2;
            if(a[mid]==value)             //取中间量
                return mid;
            else if(a[mid]>value)
                high = mid-1;            //从前半部分查找
            else
                low = mid+1;            //从后半部分查找
        }
        return -1;
    }
    
    //二分查找，递归方法
    int BinarySearch2(int a[], int value, int low, int high)
    {
        
        if(low>high)
            return -1;
        int mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        else if(a[mid]>value)
            return BinarySearch2(a, value, low, mid-1);
        else
            return BinarySearch2(a, value, mid+1, high);
    }

### 插值查找 ###

**算法简介**  
在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？  
打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。  
经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：　  
 m i d = ( l o w + h i g h ) / 2 , 即 m i d = l o w + 1 / 2 ( h i g h − l o w ) mid=(low+high)/2, 即mid=low+1/2(high-low) mid=(low\+high)/2,即mid=low\+1/2(high−low)  
通过类比，我们可以将查找的点改进为如下：  
　　 mid=low+(key-a\[low\])/(a\[high\]-a\[low\])\*(high-low)，  
也就是将上述的**比例参数1/2**改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。  
**查找成功或者失败的时间复杂度均为 O ( l o g 2 ( l o g 2 n ) ) O(log\_2(log\_2^n)) O(log2(log2n)),最坏情况可能需要 O （ n ） O（n） O（n）**。  
　  
**算法思想**  
基于二分查找算法，**将查找点的选择改进为自适应选择**，可以提高查找效率。当然，**插值查找也属于有序查找**。  
注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

**算法实现**

//插值查找，类似二分查找，只是mid计算方式不同，此处给出递归方法，一般方法也和上述二分查找类似
    int InsertionSearch(int a[], int value, int low, int high)
    {
        
        if(low>high)
            return -1;
        int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
        if(a[mid]==value)
            return mid;
        else if(a[mid]>value)
            return InsertionSearch(a, value, low, mid-1);
        else
            return InsertionSearch(a, value, mid+1, high);
    }

### 分块查找 ###

**算法简介**  
要求是**顺序表**，分块查找又称**索引顺序查找**，它是顺序查找的一种改进方法。  
时间复杂度： O ( l o g ( m ) + n / m ) O(log(m)+n/m) O(log(m)\+n/m)

**算法思想**

1.  将n个数据元素"按块有序"划分为m块（m ≤ n）。
2.  每一块中的结点不必有序，但块与块之间必须"按块有序"；
3.  即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；
4.  而第2块中任一元素又都必须小于第3块中的任一元素，……

![1.png][]

**算法流程**

1.  先选取各块中的最大关键字构成一个索引表；
2.  查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；
3.  在已确定的块中用顺序法进行查找。

**平均查找长度**  
将长度为n的查找表均匀分为m块，每块有s个记录，在等概率的情况，平均查找长度计算如下：

1.  **索引和块内均用顺序查找**  
     A S L = m + 1 2 + s + 1 2 = s 2 + 2 s + n 2 s , ( m s = n ) ASL= \\frac\{m+1\}\{2\} + \\frac\{s+1\}\{2\} = \\frac\{s^2+2s+n\}\{2s\},(ms=n) ASL=2m\+1\+2s\+1=2ss2\+2s\+n,(ms=n)  
    特殊的  
     当 s = n 时 ， A S L m i n = n + 1 当 s =\\sqrt\{n\}时，ASL\_\{min\} = \\sqrt\{n\}+1 当s=n时，ASLmin=n\+1
2.  **索引折半查找，块内顺序查找**

A S L = ⌈ l o g 2 ( m + 1 ) ⌉ + s + 1 2 ASL = \\left \\lceil log\_2^\{(m+1)\} \\right \\rceil + \\frac\{s+1\}\{2\} ASL=⌈log2(m\+1)⌉\+2s\+1

### 斐波那契查找 ###

这部分大致知道过程，先记录下来，以后有时间在认真研究一下=-=，主要参考[百度百科][Link 1]

**算法简介**  
斐波那契数列，又称黄金分割数列，指的是这样一个数列： 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 ⋅ ⋅ ⋅ ⋅ 1、1、2、3、5、8、13、21、···· 1、1、2、3、5、8、13、21、⋅⋅⋅⋅，在数学上，斐波那契被递归方法如下定义： F ( 1 ) = 1 ， F ( 2 ) = 1 ， F ( n ) = f ( n − 1 ) + F ( n − 2 ) （ n > = 2 ） F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2） F(1)=1，F(2)=1，F(n)=f(n−1)\+F(n−2)（n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

**斐波那契查找的时间复杂度还是 O ( l o g 2 n ) O(log\_2^n ) O(log2n)**，但是与折半查找相比，**斐波那契查找的优点是它只涉及加法和减法运算，而不用除法**，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。

**算法思想**  
也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。  
相对于折半查找，一般将待比较的key值与第 m i d = （ l o w + h i g h / 2 mid=（low+high/2 mid=（low\+high/2位置的元素比较，比较结果分三种情况：

1.  相等，mid位置的元素即为所求;
2.  大于， l o w = m i d + 1 low=mid+1 low=mid\+1;
3.  小于， h i g h = m i d − 1 high=mid-1 high=mid−1。

斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。**要求开始表中记录的个数为某个斐波那契数小1**，及 n = F ( k ) − 1 n=F(k)-1 n=F(k)−1;

开始将k值与第 F ( k − 1 ) F(k-1) F(k−1)位置的记录进行比较(及 m i d = l o w + F ( k − 1 ) − 1 mid=low+F(k-1)-1 mid=low\+F(k−1)−1),比较结果也分为三种

1.  相等，mid位置的元素即为所求
2.  大于， l o w = m i d + 1 , k − = 2 low=mid+1,k-=2 low=mid\+1,k−=2;

**说明：** l o w = m i d + 1 low=mid+1 low=mid\+1说明待查找的元素在 \[ m i d + 1 , h i g h \] \[mid+1,high\] \[mid\+1,high\]范围内， k − = 2 k-=2 k−=2 说明范围 \[ m i d + 1 , h i g h \] \[mid+1,high\] \[mid\+1,high\]内的元素个数为 n − ( F ( k − 1 ) ) = F ( k ) − 1 − F ( k − 1 ) = F ( k ) − F ( k − 1 ) − 1 = F ( k − 2 ) − 1 n-(F(k-1))= F(k)-1-F(k-1)=F(k)-F(k-1)-1=F(k-2)-1 n−(F(k−1))=F(k)−1−F(k−1)=F(k)−F(k−1)−1=F(k−2)−1个，所以可以递归的应用斐波那契查找。

1.  小于， h i g h = m i d − 1 , k − = 1 high=mid-1,k-=1 high=mid−1,k−=1。

**说明：** l o w = m i d + 1 low=mid+1 low=mid\+1说明待查找的元素在 \[ l o w , m i d − 1 \] \[low,mid-1\] \[low,mid−1\]范围内， k − = 1 k-=1 k−=1 说明范围 \[ l o w , m i d − 1 \] \[low,mid-1\] \[low,mid−1\]内的元素个数为 F ( k − 1 ) − 1 F(k-1)-1 F(k−1)−1个，所以可以递归 的应用斐波那契查找。  
　　  
 **n = F ( k ) − 1 n=F(k)-1 n=F(k)−1， 表中记录的个数为某个斐波那契数小1。这是为什么呢？**

是为了格式上的统一，以方便递归或者循环程序的编写。表中的数据是 F ( k ) − 1 F(k)-1 F(k)−1个，使用 m i d mid mid值进行分割又用掉一个，那么剩下 F ( k ) − 2 F(k)-2 F(k)−2个。正好分给两个子序列，每个子序列的个数分别是 F ( k − 1 ) − 1 F(k-1)-1 F(k−1)−1与 F ( k − 2 ) − 1 F(k-2)-1 F(k−2)−1个，格式上与之前是统一的。不然的话，每个子序列的元素个数有可能是 F ( k − 1 ) ， F ( k − 1 ) − 1 ， F ( k − 2 ) ， F ( k − 2 ) − 1 F(k-1)，F(k-1)-1，F(k-2)，F(k-2)-1 F(k−1)，F(k−1)−1，F(k−2)，F(k−2)−1个，写程序会非常麻烦。

**算法举例**  
对于斐波那契数列： 1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34 、 55 、 89 … … 1、1、2、3、5、8、13、21、34、55、89…… 1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。比如这里的89，把它想象成整个有序表的元素个数，而89是由前面的两个斐波那契数34和55相加之后的和，也就是说把元素个数为89的有序表分成由前55个数据元素组成的前半段和由后34个数据元素组成的后半段，那么前半段元素个数和整个有序表长度的比值就接近黄金比值0.618，假如要查找的元素在前半段，那么继续按照斐波那契数列来看，55 = 34 + 21，所以继续把前半段分成前34个数据元素的前半段和后21个元素的后半段，继续查找，如此反复，直到查找成功或失败，这样就把斐波那契数列应用到查找算法中了。

![2.png][]

从图中可以看出，当有序表的元素个数不是斐波那契数列中的某个数字时，需要把有序表的元素个数长度补齐，让它成为斐波那契数列中的一个数值，当然把原有序表截断肯定是不可能的，不然还怎么查找。然后图中标识每次取斐波那契数列中的某个值时(F\[k\])，都会进行-1操作，这是因为有序表数组位序从0开始的，纯粹是为了迎合位序从0开始。

**算法实现**

// 斐波那契查找.cpp   
       
    #include "stdafx.h"  
    #include <memory>  
    #include  <iostream>  
    using namespace std;  
       
    const int max_size=20;//斐波那契数组的长度  
       
    /*构造一个斐波那契数组*/   
    void Fibonacci(int * F)  
    {
          
        F[0]=0;  
        F[1]=1;  
        for(int i=2;i<max_size;++i)  
            F[i]=F[i-1]+F[i-2];  
    }  
       
    /*定义斐波那契查找法*/    
    int Fibonacci_Search(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字  
    {
          
      int low=0;  
      int high=n-1;  
         
      int F[max_size];  
      Fibonacci(F);//构造一个斐波那契数组F   
       
      int k=0;  
      while(n>F[k]-1)//计算n位于斐波那契数列的位置  
          ++k;  
       
      int  * temp;//将数组a扩展到F[k]-1的长度  
      temp=new int [F[k]-1];  
      memcpy(temp,a,n*sizeof(int));  
       
      for(int i=n;i<F[k]-1;++i)  
         temp[i]=a[n-1];  
         
      while(low<=high)  
      {
          
        int mid=low+F[k-1]-1;  
        if(key<temp[mid])  
        {
          
          high=mid-1;  
          k-=1;  
        }  
        else if(key>temp[mid])  
        {
          
         low=mid+1;  
         k-=2;  
        }  
        else  
        {
          
           if(mid<n)  
               return mid; //若相等则说明mid即为查找到的位置  
           else  
               return n-1; //若mid>=n则说明是扩展的数值,返回n-1  
        }  
      }    
      delete [] temp;  
      return -1;  
    }  
       
    int _tmain(int argc, _TCHAR* argv[])  
    {
          
        int a[] = {
        0,16,24,35,47,59,62,73,88,99};  
        int key=100;  
        int index=Fibonacci_Search(a,sizeof(a)/sizeof(int),key);  
        cout<<key<<" is located at:"<<index;  
        system("PAUSE");  
        return 0;  
    }

\*\*总结：\*\*本文主要介绍了5种常见的查找算法，在接下来的文章中，将继续介绍另外2种更重要的查找算法，**树表查找和哈希查找**。

[1.png]: https://liufan.vip/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2019-4-3-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B9%8B%E6%9F%A5%E6%89%BE/1.png
[Link 1]: https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%90%9C%E7%B4%A2/19131306?fr=aladdin
[2.png]: https://liufan.vip/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/2019-4-3-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B9%8B%E6%9F%A5%E6%89%BE/2.png