Earyant的技术博客

欢迎来到Earyant的技术博客，在这里我将与你分享新技术。

七大查找算法

发表于 更新于
本文字数： 5.6k 阅读时长 ≈ 5 分钟

原文链接

查找算法分类：

  • 1）静态查找和动态查找；
    注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
  • 2）无序查找和有序查找。
    • 无序查找：被查找数列有序无序均可；
    • 有序查找：被查找数列必须为有序数列。

1. 顺序查找

挨个查找，不用多说，时间复杂度为O(n);

2. 二分查找

  • 说明元素必须是有序的，如果是无序的则要先进行排序操作。

  • 基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

  • 复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)；
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
        //二分查找（折半查找），版本1
    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;
         if(a[mid]>value)
         high = mid-1;
         if(a[mid]<value)
         low = mid+1;
     }
         return -1;
    }
     
    //二分查找，递归版本
    int BinarySearch2(int a[], int value, int low, int high)
    {
       int mid = low+(high-low)/2;
       if(a[mid]==value)
       return mid;
       if(a[mid]>value)
       return BinarySearch2(a, value, low, mid-1);
       if(a[mid]<value)
       return BinarySearch2(a, value, mid+1, high);
    }
    ```  


    ## 3. 插值查找

    在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？

    打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。<

    同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。

    经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：

    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(log2(log2n))。

    //插值查找
    int InsertionSearch(int a[], int value, int low, int high)
    {
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
    if(a[mid]==value)
    return mid;
    if(a[mid]>value)
    return InsertionSearch(a, value, low, mid-1);
    if(a[mid]<value)
    return InsertionSearch(a, value, mid+1, high);
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101

    ## 4. 斐波那契查找

    在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

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

    0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

    大家记不记得斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。


    * 基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。

    相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况：
       * 1）相等，mid位置的元素即为所求

       * 2）>，low=mid+1;

       * 3）<，high=mid-1。

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

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

       * 1）相等，mid位置的元素即为所求

       * 2）>，low=mid+1,k-=2;

    说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。

       * 3）<，high=mid-1,k-=1。

    说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。

    复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。

    ```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 FibonacciSearch(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 main()
       {
          int a[] = {0,16,24,35,47,59,62,73,88,99};
          int key=100;
          int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
          cout<<key<<" is located at:"<<index;
          return 0;
       }

5. 树表查找

5.1 最简单的树表查找算法——二叉树查找算法。

  • 基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。

    二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树：

    1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

    2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

    3）任意节点的左、右子树也分别为二叉查找树。

    二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。

    不同形态的二叉查找树如下图所示：

    • 复杂度分析：它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡（比如，我们查找上图（b）中的“93”，我们需要进行n次查找操作）。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。

基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。

5.2 平衡查找树之2-3查找树（2-3 Tree）

2-3查找树定义：和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：

  • 1）要么为空，要么：

  • 2）对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。

  • 3）对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。

  • 2-3查找树的性质：

    1）如果中序遍历2-3查找树，就可以得到排好序的序列；

    2）在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。（这也是平衡树中“平衡”一词的概念，根节点到叶节点的最长距离对应于查找算法的最坏情况，而平衡树中根节点到叶节点的距离都一样，最坏情况也具有对数复杂度。）

    • 复杂度分析：

    2-3树的查找效率与树的高度是息息相关的。

    在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN
    在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN
    距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。

5.3 平衡查找树之红黑树（Red-Black Tree）

2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。

基本思想：红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。

欢迎关注我的其它发布渠道