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

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

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

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

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

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

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

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

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

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

顺序查找

算法简介
顺序查找又称为线性查找，是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。时间复杂度为 $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} ）$ 。

基本思路
给予一个包含 n个带值元素的数组A
1、令 L为0 ， R为 n-1 ；
2、如果L>R，则搜索以失败告终；
3、令 m (中间值元素)为 ⌊(L+R)/2⌋ (向下取整)；
4、如果 $A_{m} < T$ ，令 L为 m + 1 并回到步骤二；
5、如果 $A_{m} > 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+(key-a[low])/(a[high]-a[low])*(high-low)，
也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
查找成功或者失败的时间复杂度均为 $O (l o g_{2} (l o g_{2}^{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)$

算法思想

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

算法流程

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

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

索引和块内均用顺序查找
$A S L = \frac{m + 1}{2} + \frac{s + 1}{2} = \frac{s^{2} + 2 s + n}{2 s}, (m s = n)$
特殊的
$当 s = \sqrt{n} 时， A S L_{m i n} = \sqrt{n} + 1$
索引折半查找，块内顺序查找

$A S L = ⌈ l o g_{2}^{(m + 1)} ⌉ + \frac{s + 1}{2}$

斐波那契查找

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

算法简介
斐波那契数列，又称黄金分割数列，指的是这样一个数列： $1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 \cdot \cdot \cdot \cdot$ ，在数学上，斐波那契被递归方法如下定义： $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})$ ，但是与折半查找相比，斐波那契查找的优点是它只涉及加法和减法运算，而不用除法，而除法比加减法要占用更多的时间，因此，斐波那契查找的运行时间理论上比折半查找小，但是还是得视具体情况而定。

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

相等，mid位置的元素即为所求;
大于， $l o w = m i d + 1$ ;
小于， $h i g h = m i d - 1$ 。

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

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

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

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

小于， $h i g h = m i d - 1, k - = 1 $ 。

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

是为了格式上的统一，以方便递归或者循环程序的编写。表中的数据是 $F (k) - 1$ 个，使用 $m i d$ 值进行分割又用掉一个，那么剩下 $F (k) - 2$ 个。正好分给两个子序列，每个子序列的个数分别是 $F (k - 1) - 1$ 与 $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 \dots \dots$ （也可以从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种更重要的查找算法，树表查找和哈希查找。