数据结构——常用的查找算法

本篇讲讲数据结构里面常用的几个查找算法，数据结构理论篇系列差不多接近尾声了，接下来会分享一些比较特殊的概念，比如KMP、郝夫曼树等等，讲完概念以后会进入刷题阶段。刷题会用Python来，请持续关注。

1.顺序表查找

顺序查找又叫线性查找，是最基本的查找技术，它的关键流程为：从表中第一个或最后一个记录开始，逐个对比该记录中的关键词与待查找关键词是否相等，如果某条记录中的关键词与待查找关键词相等，则表示查找成功，返回所查找记录；如果直到最后一条记录，其关键词与待查找关键词都不相等，则查找失败。

具体实现代码如下：

int Sequential_Search(int *a,int n,int key)    //a为数组，n为要查找数组长度，key为待查找关键词{    int i;    for(i = 1;i <= n;i++)    //遍历数组内的每一条记录,元素记录是从1开始    {        if(a[i] == key)    //如果查找到，则返回记录所在位置            return i;    }    return 0;    //如果未查找到，则返回0}

上面基本版查找算法在遍历完一条记录以后，需要将下一条记录的位置i与数组长度n做一个比较，看是超出数组的范围，改进版的查找算法省略了这一步，具体实现过程：让a[0]=key,i = n表示a[0]为待查找关键词，且从数组的末尾依次往前查找，实现代码如下：

int Sequential_Search(int *a,int n,int key)    //a为数组，n为要查找数组长度，key为待查找关键词{    int i;    a[0] = key;    i = n;    while(a[i] != key)    {        i--;    }    return i;    //如果未查找到，则返回0}

2.有序表查找

有序查找是指线性表中的记录是有序的（从大到小或从小到大），且线性表是采用顺序存储的。

2.1折半查找

对于满足有序表这样存储结构的数据，我们采用的第一种方法是折半查找，又称二分查找。折半查找的基本思想是：在有序表中，先取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。实现代码：

int Binary_Search(int *a,int n,int key){    int low,high,mid;    low = 1;//定义最开始位置    high = n;//定义结束位置    while(low <= high)    {        mid = (low + high)/2;    //先折半            if(key < a[mid])              //如果查找值比中值小，结束位置变为中值-1            high = mid - 1;        else if(key > a[mid])    //如果查找值比中值大，起始位置变为中值+1            low = mid + 1;        else            return mid;              //如果相等，则说明mid就是待查找位置    }    return 0;}

2.2插值查找

折半查找很方便也很好理解，但是有的时候会增加不必要的查找次数。比如说，你要在0-10000之间查找10，如果按折半查找的话，会有多次无用查找。那么有没有什么方法可以避免这种问题的发生，也就是一开始就从待查找值附近开始查找，而没必要非要从中间位置开始查找。插值查找就是用来解决这个问题的。

就是把折半查找中的1/2变成了(key-a[low])/(a[high]-a[low]),这样就可以快速定位到待查找值附近开始查找，这种方法就叫做插值查找。

2.3斐波那契查找

在讲什么是斐波那契查找之前，先看看什么是斐波那契数列。

斐波那契数列，又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为"兔子数列"，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）

斐波那契查找算法具体步骤如下：

• 生成一个斐波那契序列的数组，便于之后使用。数组名记为f，例如f[1]=1，f[2]=1，f[3]=2，f[4]=3，f[5]=5，f[6]=8，f[7]=13，f[8]=21……
• 比较待查找数组长度n是否等于f[k]-1，其中k为满足条件的最小值，若等于，则进入下一步，若不等于则将待查找数组长度扩充到f[k]-1。
• 找到mid元素low+(f[k-1]-1)，不断进行二分比较，直到查找成功为止。

3.线性索引查找

我们前面讲的几种查找方法都是基于有序的基础上的，现实业务中，每时每刻都在产生大量新数据，如果对这些数据进行排序的话，耗费时间会很大，效率会很低。这个时候就需要想新的查找方法，就是我们这一节要讲的线性索引查找。

索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项组成，每个索引至少应包含关键字和其对应的记录在存储器中的位置信息。

索引按照结构可分为：线性索引、树形索引和多级索引。常用的主要是线性索引。所谓线性索引就是将索引项集合组织成线性结构，也称为索引表。重点介绍三种线性索引：稠密索引、分块索引和倒排索引。

3.1稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项,其中，稠密索引中的索引项一定是按照关键码有序排列的。

索引项有序，我们就可以按照前面提到的几种有序查找法先在左表中查找需要的关键词，然后再在右表中查找该关键词对应的数据项。如果我们不利用索引项的话，我们就只能在右表按照顺序查找的方式依次遍历每一个关键码。利用索引项可以大大缩短查找时间。但是如果数据集过大，索引也得数据集长度规模，这样每查找一个关键词时，都会去查找一遍很长的关键码，会大大降低查询效率。

3.2分块索引

稠密索引是因为索引项过长，会降低查询效率。那么有没有一种方法可以把索引项长度变短呢？那就是分块索引。图书馆的书架大家应该都见过，那种摆放其实就是一种分块索引，每个书架放一类书（建立一个索引），这样索引项就会大幅度缩短。

分块索引就是根据某个原则将数据分为若干块，让每一块对应一个索引项。

分块索引的索引项结构分三个数据项：

• 最大关键码，存储每一块中的最大关键字，这样就使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大；
• 存储块中国的记录个数，用于循环的时候使用；
• 用于指向块首数据元素的指针，便于开始这一块记录进行遍历。

分块索引查找顺序：

先在分块索引表中查找要查找的关键词所在的块，由于分块索引的块间是有序的，因此可以利用有序查找的方法进行查找。

根据块首指针找到相应的块，并在块中顺序查找关键码。

3.3倒排索引

我们先想想我们平常都是怎么使用搜索引擎的？我们输入一个我们想要查询的关键词，然后搜索引擎会返回一堆包含查找关键词的网页链接，然后我们根据自己需求，点击不同的网页即可。这背后利用的原理就是倒排索引。

倒排索引具体原理：

• 获取关键词，搜索引擎会爬取互联网上几乎所有的信息，然后将每条信息/每篇文档进行分词，所谓分词就是将一大段文字变为一个个关键词。
• 建立倒排索引，获取到关键词以后，我们就可以针对关键词建立倒排索引，就是将关键词与该关键词的出现位置，即哪篇文章，对应起来。除此之外，还需要指明该关键词在文章中具体的位置，为了快速飘红显示。还有关键词在一篇文章中出现的次数。
• 文章号就表示在第几篇文章中出现，出现频率表示在该篇文章中出现了几次，出现位置表示关键词在该篇文章中具体的位置。
• 索引建立好之后，当用户搜索一个关键词，先会在关键词列遍历查找关键词，然后返回该关键词对应的文章号以及出现位置。

4.二叉排序查找

二叉排序是一种动态查找表，这种表可以在查找时插入或删除数据，且不需要改变其他数据元素。

二叉排序树又称为二叉查找树，这棵树可以为空，如果不为空时有如下性质：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
• 它的左右子树也分别为二叉排序树。

二叉排序树首先是一颗二叉树，构建一颗二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。

二叉树结构定义：

typedef struct BiTNode{    int data;    //结点数据    struct BiTNode *lchild,* rchild;    //左右孩子指针}BiTNode,*BiTree;

二叉树查找实现

Status SearchBST(BiTree T,int key,BiTree f,BiTree *p){    if(!T)    //判断当前结点是否为空,如果为空，则执行    {        *p = f;        return FALSE;    }    else if(key == T -> data)    //如果待查找关键词等于该节点值，则返回结点位置    {        *p = T;        retuen TRUE;    }    else if(key < T-> data)    //如果待查找值小于结点值，则在左子树继续查找，否则在右子树查找        return SearchBST(T -> lchild,key,T,p)    else        return SearchBST(T -> rchild,key,T,p)}

4.1平衡二叉树(AVL树)

平衡二叉树是一种二叉排序树,其中每个节点的左子树和右子树的高度差至多等于1。

之所以又称AVL树是因为有两位数学家G.M.Adelsom-Velskii和E.M.Landis发明了一种解决平衡二叉树的算法。

我们将二叉树结点的左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上所有结点的平衡因子只可能是-1、0、1,只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

第一棵树是平衡二叉树，第二颗不是平衡二叉树，主要是因为平衡因子BF大于1。

注意：平衡二叉树前提是一种排序树。

4.2多路查找树（B树）

多路查找树中每一个结点的孩子数可以多于两个，且每个结点处可以存储多个元素。如下图中的根节点的左右子树均有三个孩子。

B树有一个很重要的特性就是：下层结点的关键字取值总是落在由上层结点关键字所划分的区间内，具体落在哪个区间内，由指针指向可以看出。

比如上图中，根节点的左子树3、6可以将区间划分为负无穷到3，3到6，6到正无穷；1和2则落到了负无穷到3之间，4和5则落在3到6区间内，7、8、9则落在6到正无穷区间内。

B树的查找也正是基于这一特性来的，具体查找步骤如下：

• 先让关键字key与根节点的关键字比较，如果key=ki，则查找成功。
• 若key<k[1]，则到p[0]所指示的子树中进行继续寻找。
• 若key>k[n]，则到p[n]所指示的子树中进行继续寻找。
• 若k[i]<key<k[i+1]，则到p[i]所指示的子树中继续查找。
• 如果遇到空指针，则证明查找不成功。

5.散列表（哈希表）查找

我们前面介绍的几种方法，都需要将待查找关键词与数据结构中存储的内容进行比较，如果查找成功，则返回该关键词对应的地址。如果不成功，则不返回值。

那么有没有一种方法可以不需要比较，直接返回地址的呢？

答案是有的，具体方式就是通过哈希表来查找。具体的实现原理其实就是将关键词与地址之间建立某种联系（映射），关键词相当于x,关键词对应的地址相当于y，y和x之间可以用一个函数来表示，我们把这个函数叫做散列函数，这样只要输入一个x就会得到y。不再需要去做对比。

5.1散列函数的构造方法

散列表查找的前提是数据是以散列形式存储的，所以我们首先来看看如何将数据以散列表的形式存储呢，即如何构造散列函数。

5.1.1直接定址法

直接地址法就是直接取关键词的某个线性值作为该关键词的散列地址。

f(key) = a*key + b (a,b为常数)

很多公寓编号就是采用的这种散列方法，比如208房间，你就可以知道这个房间在2楼第8个位置。

这种方法很简单，也不会出现位置冲突的情况，但是需要事先知道关键词的分布情况，适合于查找表较小且连续的情况。

5.1.2数字分析法

就是通过分析数字间的规律来分配地址。

比如我们拿每个人的手机号作为关键字，那么就可以取每个关键词（手机号）的后四位作为关键词的位置。如果公司人数过多（超过1w）的话很有可能会遇到地址冲突的情况，也就是两个人的尾号是相同的，关于地址冲突的解决方法我们后面来说。

这种方法适合处理关键字位数比较大的情况，因为位数足够大，才会不太可能出现位置冲突的情况，但是需要事先知道数据分布情况。

5.1.3平方取中法

这个方法就是字面意思，先对关键字平方，然后取中间3位数作为散列地址。

比如关键字1234的平方是1522756，那么该关键字的散列地址就是227。

这种方法适合不知道关键词的分布，而位数又不是很大的情况。

5.1.4折叠法

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数不够时可以短些),然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。

比如现在有关键字9876543210，散列表表长为3位(可以是4位)，可以将其分为4组，987|654|321|0，然后 将他们叠加求和987+654+321+0 = 1962，再求后3位得到散列地址962。

这种方法适合关键字位数较多，且事先不需要知道关键字分布的情况。

5.1.5除留取余数法

又是一个字面意思，对关键字除某个数得到的余数作为该关键字的散列地址。

f(key) = key mod p 

5.1.6随机数法

这个就更比较简单直接了，直接利用random方法。具体方法如下：

f(key) = random(key)

上面说到的这几种方法假设关键字都是数字，那如果关键字是字符该怎么办呢？其实所有的字符，不管是中文还是英文，都可以转化为数字（ASCII码或者是Unicode码）。

5.2处理散列冲突的方法

我们上面介绍的几种构建散列地址的方法中，有的方法会出现地址冲突，也就是不同关键词对应同一个散列地址，这肯定是不允许的，当出现地址冲突时，我们需要想办法去解决，接下来介绍几种解决地址冲突的方法。

5.2.1开放定址法

开放定址法就是一旦位置发生冲突，就去寻找下一个空的散列地址（直接给地址不停加1即可），只要散列表足够大，就一定会找到空的散列地址。

5.2.2再散列函数法

再散列函数就是刚开始选择一种散列地址构造方法去构造散列地址，当地址出现矛盾时，就换一种构造方法重新构造散列地址，直到把冲突解除。

5.2.3链地址法

链地址法就是当地址出现冲突时，将同一位置的不同元素以链表的形式存储，这样就会出现一个位置对应多个元素。

5.2.4公共溢出区法

公共溢出区法是建立一个溢出区表，专门用来存放那些地址发生冲突的元素。相当于把所有的元素放在两个表中。在查找的时候，先在主表里面进行查找，如果主表没有，则再去溢出表进行查找。

5.3散列表的查找实现

首先需要定义一个散列表结构HashTable,这个结构用来存储关键字和关键字对应的散列地址，具体定义如下：

typedef struct{    int *elem;    //数据元素存储地址    int count;    //当前数据元素个数}HashTable;int m = 0；    //散列表表长，是一个全局变量

有了结构（容器）以后，我们就可以对散列表进行初始化，具体定义如下：

Status InitHashTable(HashTable *H){    int i;    m = HASHSIZE;    H -> count = m;    H -> elme = (int *)malloc(m*sizeof(int));    for(i = 0;i < m;i ++)        H -> elme[i] = NULLKEY;    return OK;}

为了在插入数据时，计算每个关键字对应的散列地址，我们需要定义一个散列函数，具体定义如下：

int Hash(int key){    return key % m;    //这里用过的除留取余法，也可也是其他方法}

散列表初始化好了，散列函数也定义好了，这个时候就可以往散列表里面加数据了，具体实现如下：

void InsertHash(HashTable *H,int key){    int addr = Hash(key);    //获取散列地址    while(H -> elem[addr] ! = NULLKEY)    //如果散列地址不为空，说明地址冲突        addr = (addr + 1) % m;    //开放寻址，寻找下一个不冲突的位置}

插入数据以后，就等着需要用到的时候被查找，具体实现代码如下：

Status SearchHash(HashTable H,int key,int *addr){    *addr = Hash(key);    //求散列地址    while(H.elem[*addr] != key)    //如果该散列地址对应的关键字与实际关键字不等，则冲突    {        *addr = (*addr + 1) % m;    //开放寻址        if(H.elem[*addr] == NULLKEY) || *addr == Hash(key))        {            return UNSUCESS;    //说明关键字不存在        }    }    return SUCCESS;} 

End.

爱数据网专栏作者：张俊红

作者介绍：一个数据科学路上的学习者、实践者、传播者

个人公众号：俊红的数据分析之路