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

查找(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 = <munderover> i = 1 n </munderover> P i C i ASL = \sum_{i=1}^{n}P_{i}C_{i} ASL=i=1nPiCi
   P i P_i Pi:查找表中第i个数据元素的概率,一般等概率为 1 n \frac{1}{n} n1
   C i C_i​ Ci:找到第i个数据元素时已经比较过的次数。

顺序查找

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

基本思路

从第一个元素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) Olog2n

基本思路
给予一个包含 n个带值元素的数组A
1、 令 L为0 , R为 n-1 ;
2、 如果L>R,则搜索以失败告终 ;
3、 令 m (中间值元素)为 ⌊(L+R)/2⌋ (向下取整)
4、 如果 A m &lt; T A_m&lt;T Am<T,令 L为 m + 1 并回到步骤二 ;
5、 如果 A m &gt; T A_m&gt;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(highlow)
通过类比,我们可以将查找的点改进为如下:
   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) On
 
算法思想
基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,插值查找也属于有序查找
注:对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。

算法实现

//插值查找,类似二分查找,只是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. 先选取各块中的最大关键字构成一个索引表;
  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

斐波那契查找

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

算法简介
斐波那契数列,又称黄金分割数列,指的是这样一个数列: 1 1 2 3 5 8 13 21 1、1、2、3、5、8、13、21、···· 1123581321,在数学上,斐波那契被递归方法如下定义: F ( 1 ) = 1 F ( 2 ) = 1 F ( n ) = f ( n 1 ) + F ( n 2 ) n &gt; = 2 F(1)=1,F(2)=1,F(n)=f(n-1)+F(n-2) (n&gt;=2) F(1)=1F(2)=1F(n)=f(n1)+F(n2)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=mid1

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

开始将k值与第 F ( k 1 ) F(k-1) F(k1)位置的记录进行比较(及 m i d = l o w + F ( k 1 ) 1 mid=low+F(k-1)-1 mid=low+F(k1)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(k1))=F(k)1F(k1)=F(k)F(k1)1=F(k2)1个,所以可以递归的应用斐波那契查找。

  1. 小于, h i g h = m i d 1 , k = 1 high=mid-1,k-=1​ high=mid1,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,mid1]范围内, k = 1 k-=1 k=1 说明范围 [ l o w , m i d 1 ] [low,mid-1] [low,mid1]内的元素个数为 F ( k 1 ) 1 F(k-1)-1 F(k1)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(k1)1 F ( k 2 ) 1 F(k-2)-1 F(k2)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(k1)F(k1)1F(k2)F(k2)1个,写程序会非常麻烦。

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

从图中可以看出,当有序表的元素个数不是斐波那契数列中的某个数字时,需要把有序表的元素个数长度补齐,让它成为斐波那契数列中的一个数值,当然把原有序表截断肯定是不可能的,不然还怎么查找。然后图中标识每次取斐波那契数列中的某个值时(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种更重要的查找算法,树表查找和哈希查找