查找_查找算法 - CSDN
精华内容
参与话题
  • 数据结构--七大查找算法总结

    万次阅读 多人点赞 2019-06-06 11:53:46
    查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法,说是七种,其实二分查找、插值查找以及斐波那契查找...

      查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法,说是七种,其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。

      查找定义:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。

      查找算法分类:

      1)静态查找和动态查找;

        注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

      2)无序查找和有序查找。

        无序查找:被查找数列有序无序均可;

        有序查找:被查找数列必须为有序数列。

      平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。

      对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。
      Pi:查找表中第i个数据元素的概率。
      Ci:找到第i个数据元素时已经比较过的次数。

    1. 顺序查找

      说明:顺序查找适合于存储结构为顺序存储或链接存储的线性表。

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

      复杂度分析: 

      查找成功时的平均查找长度为:(假设每个数据元素的概率相等) ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
      当查找不成功时,需要n+1次比较,时间复杂度为O(n);

      所以,顺序查找的时间复杂度为O(n)。

      C++实现源码:

    //顺序查找

    int SequenceSearch(int a[], int value, int n)
    {
        int i;
        for(i=0; i<n; i++)
            if(a[i]==value)
                return i;
        return -1;
    }


    2. 二分查找

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

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

      复杂度分析:最坏情况下,关键词比较次数为log2(n+1),且期望时间复杂度为O(log2n)

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

      C++实现源码:

    //二分查找(折半查找),版本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(low > high)
            return -1;
        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))。

      C++实现源码:

    //插值查找
    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);
    }

     

    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)。

      C++实现源码:

    // 斐波那契查找.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 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还要大。

    Definition of 2-3 tree

      2-3查找树的性质:

      1)如果中序遍历2-3查找树,就可以得到排好序的序列;

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

      性质2)如下图所示:

     

      复杂度分析:

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

    • 在最坏的情况下,也就是所有的节点都是2-node节点,查找效率为lgN
    • 在最好的情况下,所有的节点都是3-node节点,查找效率为log3N约等于0.631lgN

      距离来说,对于1百万个节点的2-3树,树的高度为12-20之间,对于10亿个节点的2-3树,树的高度为18-30之间。

      对于插入来说,只需要常数次操作即可完成,因为他只需要修改与该节点关联的节点即可,不需要检查其他节点,所以效率和查找类似。下面是2-3查找树的效率:

    analysis of 2-3 tree

     

      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的左子节点。这种做法的好处是查找的时候不用做任何修改,和普通的二叉查找树相同。

    Red black tree

      红黑树的定义:

      红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:

    • 红色节点向左倾斜
    • 一个节点不可能有两个红色链接
    • 整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。

      下图可以看到红黑树其实是2-3树的另外一种表现形式:如果我们将红色的连线水平绘制,那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。

    1-1 correspondence between 2-3 and LLRB

      红黑树的性质整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同(2-3树的第2)性质,从根节点到叶子节点的距离都相等)。

      复杂度分析:最坏的情况就是,红黑树中除了最左侧路径全部是由3-node节点组成,即红黑相间的路径长度是全黑路径长度的2倍。

      下图是一个典型的红黑树,从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍:

    a typic red black tree

      红黑树的平均高度大约为logn。

      下图是红黑树在各种情况下的时间复杂度,可以看出红黑树是2-3查找树的一种实现,它能保证最坏情况下仍然具有对数的时间复杂度。

      红黑树这种数据结构应用十分广泛,在多种编程语言中被用作符号表的实现,如:

    • Java中的java.util.TreeMap,java.util.TreeSet;
    • C++ STL中的:map,multimap,multiset;
    • .NET中的:SortedDictionary,SortedSet 等。

      5.4 B树和B+树(B Tree/B+ Tree)

      平衡查找树中的2-3树以及其实现红黑树。2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key。

      维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库文件系统

      B树定义:

      B树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

    • 根节点至少有两个子节点

    • 每个节点有M-1个key,并且以升序排列

    • 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间

    • 其它节点至少有M/2个子节点

      下图是一个M=4 阶的B树:

      可以看到B树是2-3树的一种扩展,他允许一个节点有多于2个的元素。B树的插入及平衡化操作和2-3树很相似,这里就不介绍了。下面是往B树中依次插入

    6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

    的演示动画:

      B+树定义:

      B+树是对B树的一种变形树,它与B树的差异在于:

    • 有k个子结点的结点必然有k个关键码;
    • 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
    • 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

      如下图,是一个B+树:

    B Plus tree

     

      下图是B+树的插入动画:

     

      B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

      B+ 树的优点在于:

    • 由于B+树在内部节点上不好含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
    • B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

      但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

      下面是B 树和B+树的区别图:

    Different between B tree and B plus tree

      B/B+树常用于文件系统和数据库系统中,它通过对每个节点存储个数的扩展,使得对连续的数据能够进行较快的定位和访问,能够有效减少查找时间,提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中,如:

    • Windows:HPFS文件系统;
    • Mac:HFS,HFS+文件系统;
    • Linux:ResiserFS,XFS,Ext3FS,JFS文件系统;
    • 数据库:ORACLE,MYSQL,SQLSERVER等中。

      有关B/B+树在数据库索引中的应用,请看张洋的MySQL索引背后的数据结构及算法原理这篇文章,这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍,推荐阅读。

      树表查找总结:

      二叉查找树平均查找性能不错,为O(logn),但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化,我们可以使用平衡查找树。平衡查找树中的2-3查找树,这种数据结构在插入之后能够进行自平衡操作,从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难,红黑树是2-3树的一种简单高效的实现,他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树,应用非常广泛,很多编程语言的内部实现都或多或少的采用了红黑树。

      除此之外,2-3查找树的另一个扩展——B/B+平衡树,在文件系统和数据库系统中有着广泛的应用。

     

    6. 分块查找

      分块查找又称索引顺序查找,它是顺序查找的一种改进方法。
      算法思想:将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……
      算法流程:
      step1 先选取各块中的最大关键字构成一个索引表;
      step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。


    7. 哈希查找

      什么是哈希表(Hash)?

      我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素"分类",然后将这个元素存储在相应"类"所对应的地方。但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。

      总的来说,"直接定址"与"解决冲突"是哈希表的两大特点。

      什么是哈希函数?

      哈希函数的规则是:通过某种转换关系,使关键字适度的分散到指定大小的的顺序结构中,越分散,则以后查找的时间复杂度越小,空间复杂度越高。

      算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

      算法流程:

      1)用给定的哈希函数构造哈希表;

      2)根据选择的冲突处理方法解决地址冲突;

        常见的解决冲突的方法:拉链法和线性探测法。详细的介绍可以参见:浅谈算法和数据结构: 十一 哈希表

      3)在哈希表的基础上执行哈希查找。

      哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

      复杂度分析

      单纯论查找复杂度:对于无冲突的Hash表而言,查找复杂度为O(1)(注意,在查找之前我们需要构建相应的Hash表)。

      使用Hash,我们付出了什么?
      我们在实际编程中存储一个大规模的数据,最先想到的存储结构可能就是map,也就是我们常说的KV pair,经常使用Python的博友可能更有这种体会。使用map的好处就是,我们在后续处理数据处理时,可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表,那我们在获取了超高查找效率的基础上,我们付出了什么?

      Hash是一种典型以空间换时间的算法,比如原来一个长度为100的数组,对其查找,只需要遍历且匹配相应记录即可,从空间复杂度上来看,假如数组存储的是byte类型数据,那么该数组占用100byte空间。现在我们采用Hash算法,我们前面说的Hash必须有一个规则,约束键与存储位置的关系,那么就需要一个固定长度的hash表,此时,仍然是100byte的数组,假设我们需要的100byte用来记录键与位置的关系,那么总的空间为200byte,而且用于记录规则的表大小会根据规则,大小可能是不定的。

      Hash算法和其他查找算法的性能对比:

    search method efficient conclusion

    展开全文
  • 常见查找算法

    千次阅读 2018-05-28 10:38:32
    一、顺序查找二、折半查找(二分查找)基本思路: 选定这批数中居中位置的一个数 与所查数进行比较, 看是否为所找之数, 若不是,利用数据的有序性,可以决定所找的数是在选定前还是在之后, 从而很快可以将查找范围缩小...

    一、顺序查找


    二、折半查找(二分查找)

    基本思路: 选定这批数中居中位置的一个数 与所查数进行比较, 看是否为所找之数, 若不是,利用数据的有序性,可以决定所找的数是在选定前还是在之后, 从而很快可以将查找范围缩小一半. 以同样的方法在选定的区域进行查找,每次都会将查找范围缩小一半,从而可以快速的找到所查找之数.




    #define Length 10
    
    int main()
    {
    	// 创建数组
    	int arr[Length] = {5, 9, 14, 28, 35, 56, 74, 89, 92, 103};
    	int number, low, mid, high, flag;
    	low = 0;
    	high = Length - 1;
    	flag = 0;
    
    	printf("Please input a number:\n");
    	scanf("%d",&number);
    
    	if (number < arr[0] || number > arr[Length - 1])	
    	{
    		printf("There is not %d\n", number);
    	}
    
    	while(low <= high)	
    	{
    		mid = (low + high) / 2;
    		// 如果输入的数等于序列中间的数,就查找成功
    		if (number == arr[mid])
    		{
    			flag = 1;
    			break;
    
    		} else if (number < arr[mid]) {
    
    			high = mid - 1;
    
    		} else {
    
    			low = mid + 1;
    
    		}
    	}
    
    	if (flag == 1)
    	{
    		printf("The index of %d is %d\n", number, mid);
    
    	} else {
    
    		printf("There is not %d\n", number);
    
    	}
    
    	printf("\n");
    
    	return 0;
    
    }

    三、二分查找树(二分排序树)



    #include <stdio.h>
    #include <stdlib.h>
    #define 0 FALSE
    #define 1 TRUE
    // 二叉树的二叉链表结点结构定义
    typedef struct BiTNode
    {
    	int data;
    	struct BiTNode *lchild, *rchild;
    } BiTNode, *BiTree;
    
    // 创建一颗二叉树: T为指向结构体指针的指针	*T为指向结构体指针	**T就表示结构体
    void createBiTree(BiTree *T)
    {
    	char c;
    
    	scanf("%c", &c);
    	if (' ' == c)	// 如果输入空格,就表示输入结束
    	{
    		*T = NULL;
    
    	} else {
    
    		*T = (BiTNode *)malloc(sizeof(BiTNode));
    		(*T)->data = c;
    		createBiTree(&(*T)->lchild);
    		createBiTree(&(*T)->rchild);
    	}
    }∫
    
    // 递归查找二插排序树 T 中是否存在 key
    // 指针 f 指向 T 的双亲, 其初始值用值为NULL
    // 若查找成功, 则指针p指向该数据元素结点, 并返回TRUE
    // 否则指针p指向查找路径上访问的最后一个结点并返回FALSE
    int searchBST(BiTree T, int key, BiTree f, BiTree *p)
    {
    	if (!T)		// 查找不成功
    	{
    		*p = f;
    		return FALSE;
    
    	} else if (key == T->data) {	// 查找成功
    
    		*p = T;
    		return TRUE;
    
    	} else if (key < T->data) {
    
    		return searchBST(T->lchild, key, T, p);	// 在左子树继续查找
    
    	} else {
    
    		return searchBST(T->rchild, key, T, p);	// 在右子树继续查找
    	}
    
    	return 0;
    }
    
    // 二叉查找树的查找算法(非递归)
    BiTree SearchBST(BiTree root, int key, BiTree *father)
    {
    	// 在root指向根的二叉查找树中查找键值为key的结点,若找到返回该点指针,否则返回NULL
    	BiTree p = root;
    	*father = NULL;
    	while(p && p->data!=key)
    	{
    		*father = p;	// 记录p的上一个结点
    		if (key < p->data)
    		{
    			p = p->lchild;
    
    		} else {
    
    			p = p->rchild;
    
    		}
    	}
    }
    
    // 二叉查找树中插入结点操作
    int InsertBST(BiTree *root, int e)
    {
    	// 在*root指向根的二叉排序树中插入一个键值为e的结点,若插入成功返回0,否则返回-1
    	BiTree s, p, f;
    	s = (BiTree)malloc(sizeof(BiTNode));	// 创建一个新的结点
    	if (s == NULL)	// 如果结点创建失败
    	{
    		return -1;
    	}
    
    	s->data = e;	// 将传入的值给新结点
    	s->lchild = NULL;
    	s->rchild = NULL;
    
    	p = SearchBST(*root, e, &f);	// 寻找插入位置
    
    	// 键值为e的结点已经在树中,不再插入
    	if (p)	
    	{
    		return -1;
    	}
    
    	// 若为空树, 键值为e的结点为树根
    	if (!f)
    	{
    		*root = s;
    
    	// 作为左孩子结点插入
    	} else if (e < f->data) {
    
    		f->lchild = s;
    
    	// 作为右孩子结点插入
    	} else {
    
    		f->rchild = s;
    
    	}
    
    	return 0;
    
    }

    展开全文
  • 几种查找方法

    千次阅读 2018-04-21 16:36:06
    在一个数组中,对于数据的查找方法有多种,下面介绍几种最常见的元素查找 1、普通查找 这是最简单粗暴的查找方式,通过遍历所有元素,找到最数组中的位置。通过代码简单实现 #include&lt;stdio.h&gt; #...

    前言

    在一个数组中,对于数据的查找方法有多种,下面介绍几种最常见的元素查找

    1、普通查找

    这是最简单粗暴的查找方式,通过遍历所有元素,找到最数组中的位置。通过代码简单实现

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define MAX 10
    
    int searchNum(int a[], int data) {
        int pos = -1;
        for(int i=0; i < MAX; i++) {
            if(a[i] == data) {
                pos = i;
                break;
            }
        }
        return pos;
    }
    int main() {
        int a[MAX];
        for(int i=0; i < MAX; i++) {
            int t = rand() % 10;
            a[i] = t;
        }
        int pos = searchNum(&a, 4);
        if(pos == -1) printf("NOT FOUND");
        else printf("the position is: %d ", pos);
        return 0;
    }

    2、普通查找(哨兵)

    我们这一次查找也是普通查找,只是我们通过采用哨兵的形式,能够使代码更加简洁。主要原理就是我们在数组的第一个a[0]放我们需要查找的元素,然后从最后一个开始向前遍历,如果发现有一个和查找元素相等,那么就说明我们已经找到了,如果一直没有发现,那么遍历的时候在遍历到a[0]的时候仍然会相等。因此我们最后的位置是0,那么就是没有找到,否则就是找到了

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define MAX 10
    
    int searchNum(int a[], int data) {
        int pos;
        for(pos=MAX; a[pos] != data; pos--);
        return pos;
    }
    int main() {
        int a[MAX];
        int data = 4;
        a[0] = data;
        for(int i=1; i < MAX; i++) {
            int t = rand() % 10;
            a[i] = t;
        }
        int pos = searchNum(&a, data);
        if(pos == 0) printf("NOT FOUND");
        else printf("the position is: %d ", pos);
        return 0;
    }

    3、二分查找

    这是最经典的查找方式,通过此种方法进行查找,需要满足两个条件,第一数据是按照顺序排列的,第二是数据必须放在数组中的。在一组有序数据中,我们先找到中间的数据,判断我们需要查找的数据和数组中间数据的大小,如果中间的数据大于我们需要查找的数据,那么就在数组前半部分进行查找,如果小于需要查找的数据,那么就在后半部分查找。

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define MAX 10
    
    int searchNum(int a[], int data) {
        int left = 0, right = MAX - 1;
        int middle = (left + right) / 2;
        int flag = 0;
        while(left <= right) {
            if(a[middle] < data) left = middle + 1;
            else if(a[middle] > data) right = middle - 1;
            else { flag = 1; break; }
            middle = (left + right) / 2;
        }
        if(flag) return middle;
        return -1;
    }
    int main() {
        int a[MAX];
        memset(a, 0, sizeof(a));
        int data = 10;
        for(int i=1; i < MAX; i++) {
            int t = rand() % 10 + 1;
            a[i] = t + a[i-1];
        }
        int pos = searchNum(&a, data);
        if(pos == -1) printf("NOT FOUND");
        else printf("the position is: %d ", pos);
        return 0;
    }
    展开全文
  • 数据结构–七大查找算法总结

    万次阅读 多人点赞 2020-04-23 15:08:01
    转 数据结构–七大查找算法总结 2017年08月15日 21:06:17 阅读数:10610 ...

      查找定义:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。

      查找算法分类:
      1)静态查找和动态查找;
        注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
      2)无序查找和有序查找。
        无序查找:被查找数列有序无序均可;
        有序查找:被查找数列必须为有序数列。
      平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。
      对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。
      Pi:查找表中第i个数据元素的概率。
      Ci:找到第i个数据元素时已经比较过的次数。

    1. 顺序查找

      说明:顺序查找适合于存储结构为顺序存储或链接存储的线性表。
      基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。
      复杂度分析: 
      查找成功时的平均查找长度为:(假设每个数据元素的概率相等) ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
      当查找不成功时,需要n+1次比较,时间复杂度为O(n);
      所以,顺序查找的时间复杂度为O(n)。
      C++实现源码:
    //顺序查找
    int SequenceSearch(int a[], int value, int n)
    {
        int i;
        for(i=0; i<n; i++)
            if(a[i]==value)
                return i;
        return -1;
    }
    

    2. 二分查找

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

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

      复杂度分析:最坏情况下,关键词比较次数为log2(n+1),且期望时间复杂度为O(log2n)

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

      C++实现源码:

    //二分查找(折半查找),版本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))。
      C++实现源码:
    //插值查找
    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);
    }
    

    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)。

      C++实现源码:

    // 斐波那契查找.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 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&gt;=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还要大。

    Definition of 2-3 tree

      2-3查找树的性质:

      1)如果中序遍历2-3查找树,就可以得到排好序的序列;

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

      性质2)如下图所示:

     

      复杂度分析:

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

    • 在最坏的情况下,也就是所有的节点都是2-node节点,查找效率为lgN
    • 在最好的情况下,所有的节点都是3-node节点,查找效率为log3N约等于0.631lgN

      距离来说,对于1百万个节点的2-3树,树的高度为12-20之间,对于10亿个节点的2-3树,树的高度为18-30之间。

      对于插入来说,只需要常数次操作即可完成,因为他只需要修改与该节点关联的节点即可,不需要检查其他节点,所以效率和查找类似。下面是2-3查找树的效率:

    analysis of 2-3 tree

     

      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的左子节点。这种做法的好处是查找的时候不用做任何修改,和普通的二叉查找树相同。

    Red black tree

      红黑树的定义:

      红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:

    • 红色节点向左倾斜
    • 一个节点不可能有两个红色链接
    • 整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。

      下图可以看到红黑树其实是2-3树的另外一种表现形式:如果我们将红色的连线水平绘制,那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。

    1-1 correspondence between 2-3 and LLRB

      红黑树的性质整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同(2-3树的第2)性质,从根节点到叶子节点的距离都相等)。

      复杂度分析:最坏的情况就是,红黑树中除了最左侧路径全部是由3-node节点组成,即红黑相间的路径长度是全黑路径长度的2倍。

      下图是一个典型的红黑树,从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍:

    a typic red black tree

      红黑树的平均高度大约为logn。

      下图是红黑树在各种情况下的时间复杂度,可以看出红黑树是2-3查找树的一种实现,它能保证最坏情况下仍然具有对数的时间复杂度。

      红黑树这种数据结构应用十分广泛,在多种编程语言中被用作符号表的实现,如:

    • Java中的java.util.TreeMap,java.util.TreeSet;
    • C++ STL中的:map,multimap,multiset;
    • .NET中的:SortedDictionary,SortedSet 等。

      5.4 B树和B+树(B Tree/B+ Tree)

      平衡查找树中的2-3树以及其实现红黑树。2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key。

      维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库文件系统

      B树定义:

      B树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

    • 根节点至少有两个子节点

    • 每个节点有M-1个key,并且以升序排列

    • 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间

    • 其它节点至少有M/2个子节点

      下图是一个M=4 阶的B树:

      可以看到B树是2-3树的一种扩展,他允许一个节点有多于2个的元素。B树的插入及平衡化操作和2-3树很相似,这里就不介绍了。下面是往B树中依次插入

    6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

    的演示动画:

      B+树定义:

      B+树是对B树的一种变形树,它与B树的差异在于:

    • 有k个子结点的结点必然有k个关键码;
    • 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
    • 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

      如下图,是一个B+树:

    B Plus tree

     

      下图是B+树的插入动画:

     

      B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

      B+ 树的优点在于:

    • 由于B+树在内部节点上不好含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
    • B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

      但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

      下面是B 树和B+树的区别图:

    Different between B tree and B plus tree

      B/B+树常用于文件系统和数据库系统中,它通过对每个节点存储个数的扩展,使得对连续的数据能够进行较快的定位和访问,能够有效减少查找时间,提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中,如:

    • Windows:HPFS文件系统;
    • Mac:HFS,HFS+文件系统;
    • Linux:ResiserFS,XFS,Ext3FS,JFS文件系统;
    • 数据库:ORACLE,MYSQL,SQLSERVER等中。

      有关B/B+树在数据库索引中的应用,请看张洋的MySQL索引背后的数据结构及算法原理这篇文章,这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍,推荐阅读。

      树表查找总结:

      二叉查找树平均查找性能不错,为O(logn),但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化,我们可以使用平衡查找树。平衡查找树中的2-3查找树,这种数据结构在插入之后能够进行自平衡操作,从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难,红黑树是2-3树的一种简单高效的实现,他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树,应用非常广泛,很多编程语言的内部实现都或多或少的采用了红黑树。

      除此之外,2-3查找树的另一个扩展——B/B+平衡树,在文件系统和数据库系统中有着广泛的应用。


    6. 分块查找

      分块查找又称索引顺序查找,它是顺序查找的一种改进方法。
      算法思想:将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……
      算法流程:
      step1 先选取各块中的最大关键字构成一个索引表;
      step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。


    7. 哈希查找

      什么是哈希表(Hash)?

      我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素"分类",然后将这个元素存储在相应"类"所对应的地方。但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
      总的来说,"直接定址"与"解决冲突"是哈希表的两大特点。

      什么是哈希函数?

      哈希函数的规则是:通过某种转换关系,使关键字适度的分散到指定大小的的顺序结构中,越分散,则以后查找的时间复杂度越小,空间复杂度越高。

      算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

      算法流程:

      1)用给定的哈希函数构造哈希表;
      2)根据选择的冲突处理方法解决地址冲突;
        常见的解决冲突的方法:拉链法和线性探测法。详细的介绍可以参见:浅谈算法和数据结构: 十一 哈希表
      3)在哈希表的基础上执行哈希查找。
      哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

      复杂度分析

      单纯论查找复杂度:对于无冲突的Hash表而言,查找复杂度为O(1)(注意,在查找之前我们需要构建相应的Hash表)。

      使用Hash,我们付出了什么?
      我们在实际编程中存储一个大规模的数据,最先想到的存储结构可能就是map,也就是我们常说的KV pair,经常使用Python的博友可能更有这种体会。使用map的好处就是,我们在后续处理数据处理时,可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表,那我们在获取了超高查找效率的基础上,我们付出了什么?

      Hash是一种典型以空间换时间的算法,比如原来一个长度为100的数组,对其查找,只需要遍历且匹配相应记录即可,从空间复杂度上来看,假如数组存储的是byte类型数据,那么该数组占用100byte空间。现在我们采用Hash算法,我们前面说的Hash必须有一个规则,约束键与存储位置的关系,那么就需要一个固定长度的hash表,此时,仍然是100byte的数组,假设我们需要的100byte用来记录键与位置的关系,那么总的空间为200byte,而且用于记录规则的表大小会根据规则,大小可能是不定的。

      Hash算法和其他查找算法的性能对比:

    search method efficient conclusion

    展开全文
  • 第六章 -查找

    千次阅读 2018-09-23 15:12:06
    1.下列叙述中,不符合m阶B树定义要求的是(D)。 根结点最多有m棵子树 所有叶结点都在同一层上 ...2.已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找查找一个 L中 不...
  • 漫画算法:5 分钟搞明白红黑树到底是什么?

    千次阅读 多人点赞 2019-08-05 16:30:23
    作者 |调皮的阿广 责编 | 屠敏 ...红黑树就是一种平衡的二叉查找树,说他平衡的意思是他不会变成“瘸子”,左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外,还具体下列的特性: 1...
  • 折半查找判定数及平均查找长度

    万次阅读 多人点赞 2016-07-06 13:28:31
    折半查找判定数及平均查找长度 折半查找的过程看,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该记录在表中的位置。通常称这个描述折半查找二叉树的过程称为折半查找判定树。 ...
  • Linux命令find的35个实例

    万次阅读 2017-04-05 08:40:05
    注:本文内容参考《35 Practical Examples of Linux Find Command》  ... Linux 查找命令是Linux系统中最重要和最常用的命令之一...查找用于根据与参数匹配的文件指定的条件来搜索和查找文件和目录列表的命令。查找
  • Eclipse的各种查找,类的查找,方法查找快捷键

    万次阅读 多人点赞 2018-07-05 14:27:12
    综合查找 Ctrl + H 这是一种综合查找 ,可以用来查找 一个方法的引用,或者某些特殊的标识,还可以通过注释里面的关键字查到想要的内容3,CTRL + F 这种查找是单页面的 查找某些特定的字符查找到字符然后 替换4....
  • 平均查找长度详解

    万次阅读 多人点赞 2016-04-11 21:49:42
    1.顺序查找: 从表的一端开始,顺序扫描线性表,依次将扫描到的节点关键字和给定值k相比较。 等概率条件下...平均查找长度:ASL = (n+....+2+1)/n= (n+1)/2。 2.二分法查找: 前提是线性表是有序表。假设数据是...
  • 折半查找判定树及平均查找长度

    万次阅读 多人点赞 2016-01-08 18:16:27
    折半查找判定树及平均查找长度 从折半查找的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,对子表继续上述操作。所以,对表中每个记录的查找过程,可用二叉树来描述,二叉树中的每个...
  • centos 中查找文件、目录、内容

    万次阅读 2019-09-09 13:37:20
    1、查找文件 find / -name 'filename' 2、查找目录 find / -name 'path' -type d 3、查找内容 find . | xargs grep -ri 'content' //find . | xargs grep -ril 'content' 只显示文件名称...
  • 数据结构---平均查找长度ASL的相关计算技巧

    万次阅读 多人点赞 2019-12-06 09:32:09
    个人总结的有关考研数据结构中平均查找长度ASL的三种计算小技巧:1.顺序查找法的平均查找长度为:(n+1)/2 2.散列表的查找成功和查找不成功的平均查找长度 技巧(线性探测法和链地址法): ① 查找成功时的比较...
  • Linux find查找文件及文件夹命令

    万次阅读 2018-09-18 10:47:10
    find的主要用来查找文件,查找文件的用法我们比较熟悉,也可用它来查找文件夹,用法跟查找文件类似,只要在最后面指明查找的文件类型 -type d,如果不指定type类型,会将包含查找内容的文件和文件夹一起输出。...
  • linux中查找包含指定内容的文件

    万次阅读 2018-03-14 15:18:25
    为了防止自己记不住,也方便自己查找,特此记录在博客中查找包含指定内容的文件就是用grep这个命令grep 'name' -r / grep '指定内容' -r 目录上述命令就是在根目录下递归查找包含name内容的文件 -r 递归查找文件 -...
  • 二分查找(折半查找

    万次阅读 多人点赞 2020-05-12 15:21:07
    二分查找是一种算法,其输入是一个有序的元素列表(必须是有序的),如果查找的元素包含在列表中,二分查找返回其位置,否则返回NULL 比如说有一个1-100的数字,我随机的选择其中一个数字(假设为60),你需要以...
  • Shell中find命令查找指定文件或目录

    万次阅读 2018-06-13 23:29:14
    find命令搜索指定文件或目录 描述 搜索文件或目录 ...find [命令选项] [路径] [表达式选项] ... 查找空白文件或目录 ... 按组查找 ... 按文档名称查找 ... 按文档名称查找,且不区分大小写 -mtime ...
  • 查找定义:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。 查找表按照操作方式来分有两大种:静态查找表和动态查找表。 动态查找表:在查找过程中同时插入查找表中不存在的数据...
  • source insight的查找功能

    万次阅读 多人点赞 2014-07-24 14:59:06
    source insight是一款很好的c语言的...查找功能使用十分频繁,选项较多,与其它软件的查找功能也类似,下面对英文版的查找功能,做简单说明: 查找参数: whole words only : 全字匹配查找 case sensitive : 区
  • java实现二分查找-两种方式

    万次阅读 多人点赞 2017-10-09 01:14:27
    二分查找是一种查询效率非常高的查找算法。又称折半查找。 起初在数据结构中学习递归时实现二分查找,实际上不用递归也可以实现,毕竟递归是需要开辟额外的空间的来辅助查询。本文就介绍两种方法 二分查找算法...
1 2 3 4 5 ... 20
收藏数 2,713,703
精华内容 1,085,481
关键字:

查找