七大查找算法的理解与实现

该文的“兄弟文章”–八大经典排序算法，可点击链接进行查阅。

查找是在给定的数据中，寻找特定所需的元素，在计算机应用中，查找是常用的基本运算。在数据结构与算法中，查找也是必须要掌握的基本技能。本文将介绍7类基本的查找算法，希望对掌握这一基本技能有所帮助。

这里介绍的7类基本查找方法关系如下所示：

1. 线性查找

基本思想：顺序查找也称为线形查找，用逐一比较的办法顺序查找关键字。

说明：

• 顺序查找是大家最熟悉的查找策略，对于小规模的数据，顺序查找是个不错的选择。
• 平均查找时间：1/n(1+2+3+…+n) = (n+1)/2
• 时间复杂度O(n)

//顺序查找
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与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。

说明：

• 二分查找的序列必须是有序序列
• 二分查找有两种实现方式，一种是折半查找，一种是递归版本。
• 时间复杂度为O(log2n)

两种方式的二分查找的实现代码：

//二分查找（折半查找），版本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;//(low + high) /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);
}
#include<iostream>
using namespace std;
int main()
{
   
    int a[10] = {
   11, 21, 31, 41, 51, 61, 71, 81, 91, 101};
    int num = BinarySearch1(a, 101, 10);
    cout<<"num: "<<num<<endl;
    num = BinarySearch2(a, 101,0, 10);
    cout<<"num: "<<num<<endl;
    return 1;
}

3. 插值查找

基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，查值查找也属于有序查找。

说明：

• 是一种二分查找的改进版本，每次不一定从中间开始找。

• 时间复杂度均为O(log2(log2n))

• 二分查找：中间值下标middle的计算公式为：
  middle = (left + right) / 2; // 或者middle = left + (right - left) / 2;

• 插值算法：对这个计算公式进行了改进，改进后middle更接近与被查询值，可以有效地减少比对次数，提升查询效率。
  middle=left + (key-a[left]) / (a[right] - a[left]) * (right - left)；

只需要对二分查找的mid公式进行修改即可：

int InsertionSearch(int a[], int value, int n)
{
   
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
   
        int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

#include<iostream>
using namespace std;
int main()
{
   
    int a[10] = {
   11, 21, 31, 41, 51, 61, 71, 81, 91, 101};
    int num = InsertionSearch(a, 101, 10);
    cout<<"num: "<<num<<endl;
    return 1;
}

4. 斐波那契查找

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

说明：

• 随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，也就是黄金分割比例。
• 时间复杂度为O(log2n)

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

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

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

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

说明:low=mid+1说明待查找的元素在[mid+1,hign]范围内，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 个，所以可以递归 的应用斐波那契查找

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

5. 哈希查找

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数或者哈希函数，存放记录的数组称做散列表。

散列函数或哈希函数f(key) 的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。哈希函数有6种常见的构造方法，如下所示。

1. 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即hash(k) = k 或 hash(k) = a · k + b，其中a、b为常数

哈希地址：f(key) = a*key+b (a,b为常数)
这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道 key的分布情况，适合查找表较小并且连续的情况。

2. 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

若我们现在要存储某家公司员工登记表，如果用手机号码作为 key，那么极有可能前7位都是相同的，所以我们选择最后四位作为 f(key) 就是不错的选择。

3. 平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

故名思义，比如 key 是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为 f(key) 。

4. 折叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。

折叠法是将 key 从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表的表长，取后几位作为 f(key) 。比如我们的 key 是 9876543210，哈希表的表长为3位，我们将 key 分为4组，987|654|321|0 ，然后将它们叠加求和 987+654+321+0=1962，再取后3位即得到 f(key) = 962 。

5. 随机数法

哈希地址：f(key) = random(key) 这里 random 是随机函数，当 key 的长度不等时，采用这种方法比较合适。

6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 hash(k) = k mod p， p<=m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。

哈希地址：f(key) = key mod p (p<=m) m为哈希表表长。这种方法是最常用的哈希函数构造方法。下面的代码中也使用了这种方法。

• 哈希函数冲突的两种解决办法：

1. 开放地址法

就是一旦发生了冲突，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总是能找到，然后将记录插入。这种方法是最常用的解决冲突的方法。

下图中，“Snadra Dee”和“John Smith”的哈希值都是152，所以将“Snadra Dee”移到下一地址153。而
“Sandra Dee”原本在153位置，153已经被占据，所以它需要挪到154上面去。

2. 链地址法：

首先将没有冲突的地址放在一维数组中，如果有冲突的地址，则将形成冲突的地址组成一个链表。

链地址法效果如下所示：

6. 树表查找

树表查找方法很多，根据树的结构有二叉树查找、平衡查找树之红黑树（Red-Black Tree)、平衡查找树之2-3查找树（2-3 Tree）等。

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

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

7. 分块查找

也叫索引顺序查找，这是一种性能介于顺序查找和折半查找之同的一种查找方法。

原理：先将序列分成n个块，记录各个块的最大值和起始地址，先对索引表进行二分查找或者顺序查找，以确定待查记录在哪一块中。然后，在已确定的块中用顺序法进行查找。

转载：https://blog.csdn.net/QLeelq/article/details/116543944