【数据结构--查找】

一、查找（Searching）的概念

1.1、基本概念

查找：就是根据某个给定的值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
查找表（Search Table）： 是由同一类型数据元素（或记录）构成的集合，有静态查找表和动态查找表。
静态查找表（Static Search Table）： 只做查找操作的查找表，主要操作为：
（1）查询某个“特定的”数据元素是否在查找表中；
（2）检索某个“特定的”数据元素和各种属性。
动态查找表（Dynamic Search Table）： 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素，
（1）查找时插入不存在的数据元素；
（2）查找时删除已存在的数据元素。
关键字（Key）： 数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如，在一个由学生元素构成的数据元素集合中，学生元素中“学号”这一数据项的值唯一地标识一位学生。

1.2、算法的评价指标

平均查找长度（Average Search Length）： 在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度，则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为：
$ASL=\sum_{i=1}^{n} P_{i}C_{i}$
式中，n是查找表的长度， $P_{i}$ 是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等， $P_{i}=1/n$ ， $C_{i}$ 是找到第i个数据元素所需要进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。
既然是进行查找，那必然就有查找成功和查找失败两种结果，对于两种结果进行分析均是用平均查找长度，但是注意计算比较次数的问题，由例子来分辨：
①查找成功的平均查找长度：

解释：若给定值就是根结点的关键字，那么查找1次就成功；若是第二层的关键字，就需要再查完第一层（已经比较了1次）之后，在第二层进行第2次比较，共2次；依次类推，若在第三层，则需要1+1+1=3次；上图（左树）一共有四层，则第四层的查找次数就为4次，默认每个数据元素的查找概率相同的情况下，根据每层的数据元素个数，可以列出 $A S L = (1 * 1 + 2 * 2 + 3 * 4 + 4 * 1) /8 = 2.625$ ；
②查找失败的平均查找长度：

解释：何为查找失败，也就是所查找的范围内没有目标值，而树的查找过程是从根结点到叶结点，一直查，直到比较完所有的结点，没有找到，就失败。以上图（左树）为例，查找一个目标值一直查到21了都没有符合的，那么所查值既然不等于21，那就是大于或者小于，就给有两种情况，同理，每一个叶结点都满足这种推理，所以可以列出 $A S L = (3 * 7 + 4 * 2) /9 = 3.22$ ，因为有9种失败的情况，所以除以9。

二、顺序查找

2.1、算法思想

顺序查找（Sequential Search）又叫做线性查找，是基本的查找技术，作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到的某个元素的关键字满足给定条件。则查找成功，返回该元素在线性表中的位置，若已经查找到线性表另一端，但还没查找到符合条件的元素，则返回查找失败的信息。

2.2、算法实现

2.2.1、常规顺序查找

//查找表的数据结构（顺序表）
typedef struct{
    ElemType *elem;//动态数组的基址
    int length;//表的长度
}SSTable;

//顺序查找
int Seq_Search(SSTable ST, ElemType key){
    int i;
    for(i=0;i<ST.length && ST.elem[i] != key; ++i);
    //若i等于表长，说明未在表中找到目标值，即查找失败，返回-1，若不等就跳出了循环，说明找到了目标值，返回i
    return i = ST.length ? -1 : i;
}

在这里插入图片描述

2.2.2、带哨兵的顺序查找

从后往前进行查找，在下标为0处添加哨兵，减少了对越界的判断

typedef struct{
    ElemType *elem;
    int length;
}SSTable;

//带哨兵的顺序查找
int Seq_Search(SSTable ST, int key){
    int i;
    ST.elem[0] = key;
    for(int i = ST.length; ST.elem[i] != key; --i);
    return i;
}

在这里插入图片描述

2.3、效率分析

每个元素查找的概率都为 $1/ n$ ，第一个元素查找成功需要进行的查找为1次，第二个为2次，…以此类推，第n个就为n次， $ASL_{成功}=(1+2+3+4+...+n)/n=(n+1)/2$ $ASL_{失败}=n+1$ 。

2.4、优化

2.4.1、针对有序表

查找成功的ASL计算无变化，若有序的话能够尽可能在前期查找中就判断出是否存在目标值，就不需要一定要判断到最后一个元素。
在这里插入图片描述

2.4.2、被查效率不相等

在这里插入图片描述

三、折半查找

3.1、算法思想

折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关健值相等，则查找成功；若给定值小于中间记录的关健值，则在中间记录的左半区继续查找；若给定值大于中间记录的关键值，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

3.2、算法实现

//查找表的数据结构（顺序表）
typedef struct{
    ElemType *elem;//动态数组的基址
    int length;//表的长度
}SSTable;
int Binary_Search(SSTable ST, int key ){
    int left = 0;
    int right = ST.length - 1;
    int mid = 0;
    while(left <= right){
        mid = left + (right - left)/2;
        if(key == ST.elem[mid])
            return mid;
        else if(key < ST.elem[mid])
            right = mid - 1;
        else 
            left = mid + 1;
    }
    return -1;//查找失败，返回-1
}

3.3、效率分析

在这里插入图片描述

3.3.1、判定树的构造

在这里插入图片描述

3.4、拓展

在这里插入图片描述

四、分块查找

4.1、算法思想

分块查找（Blocking Search）又称索引顺序查找，它吸取了顺序查找和折半查找的优点，既有动态结构，又适于快速查找。

分块查找相比于前两种查找方法，需要额外建立一个“索引表”。将查找表分为若干子表（或称块），对每个子表建立一个索引项，其中包含两项内容：①关键字项：值为该子表内最大的关键字，②指针项：指示子表的第一个记录在表中的位置。每个索引项构成一个索引表，索引表按关键字有序排列。
注意：块内的的元素可以无序，但块与块之间是有序的，即第一块中最大关键字小于第二块中最大关键字，以此类推。

分块查找过程分为两步：

先确定记录所在的块；
在块中进行顺序查找来查所需记录。

找所在块时，因为块间是有序的，所以可采用顺序查找也可采用折半查找。

4.2、效率分析

分块查找的平均查找长度为：
$ASL_{成功}=L_{b}+L_{w}$
其中， $L_{b}$ 为查找索引表所在块的平均查找长度， $L_{w}$ 为在块内查找元素的平均查找长度。

我们将长度为n的表均匀分为b块，每块含有s个记录，即 $b = [n / s]$ ；假定表中每个记录的查找概率相等，即每块的查找概率为 $1/ b$ ，块中每个记录的查找概率为 $1/ s$ 。

4.2.1、顺序查找查索引表

$ASL_{bs}=L_{b}+L_{w}=\frac{1}{b}\sum_{i=1}^{b}i+\frac{1}{s}\sum_{j=1}^{s}j=\frac{b+1}{2}+\frac{s+1}{2}$
从式中可以看出，顺序查找所确定块，与s,n均有关系，因此得，当s取得 $\sqrt{n}$ 时， $ASL_{bs}$ 的值最小，为 $\sqrt{n}+1$ 。

4.2.2、折半查找查索引表

$ASL_{bs}\approx log_{2}(\frac{n}{s}+1)+\frac{s+1}{2}$

时间复杂度：
分块查找的时间复杂度取决于块的数量以及块内元素的数量，在最坏的情况下（即目标位于最后一个块的最后一位），不仅需要查找完所有的块，也需要在最后一个块中遍历完所有的元素，因此，时间复杂度为 $O (m + n)$ ，其中m是块的数量，n是所有块中元素的数量。
空间复杂度：
分块查找的空间复杂度取决于用于存储块的辅助空间。由于每个块中的元素是无序的，所以无法通过块中的元素直接定位目标元素，需要额外的空间来存储块的索引。因此空间复杂度为 $O (m)$ ，其中m是块的数量。

4.3、拓展

在这里插入图片描述

五、散列查找

5.1、散列表

散列表是根据关键字而直接进行访问的数据结构，也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系，我们只需要通过某个函数f，使得：
$存储位置 = f （关键字）$ 那样我们就可以通过查找关键字，不需要比较就可获得需要的记录的存储位置。
f为散列函数，又称为哈希（hash）函数。按照这个思想，采用散列技术将记录存储在一块连续的存储空间内，这块连续的存储空间称为散列表或哈希表（hash table），那么关键字对应的记录存储位置被称为是散列地址。

散列函数可能会把两个或者两个以上的不同关键字映射到同一地址，称这样的情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计得好的散列函数应该尽量减少这方面的冲突；另一方面，由于这种冲突时不可避免的，所以还要设计处理冲突的方法。

理想情况下，散列查找的时间复杂度为 $O (1)$ ，即与表中元素的个数无关。

5.2、查找

在这里插入图片描述

5.3、常见的散列函数

在构造散列函数时，必须注意以下几点：

散列函数的定义域必须包含全部需要存储的关键字，而值域的范围依赖于散列表的大小或地址范围；
散列函数计算出来的地址应能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生；
散列函数应尽量简单，能够在较短时间内计算出任意关键字的散列地址。

5.3.1、除留余数法

假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用以下公式将关键字转换为散列地址，散列函数为： $H(key)=key\%p \ (p<=m)$ 可以对关键字直接取模（即取余），也可在折叠、平方后再取模。
关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上任一地址，从而尽量减少冲突的可能性。

5.3.2、直接定址法

直接取关键字的某个线性函数值为散列地址，散列函数为： $H (k ey) = k ey 或 H (k ey) = a * k ey + b$ 式中，a和b是常数，这种方法计算最简单，且不会产生冲突。适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

5.3.3、数学分析法

例如当身份证证号为关键字时，这串数字是有规则的，无需将整个身份证号全部当做散列地址，这时我们给关键字进行抽取，抽取方法是使用关键字的一部分来计算散列地址的方法。适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀，就可以考虑用这个方法。

5.3.4、平方取中法

假设关键字是1234，那么它的平方就是1522756，取中即抽取中间的3位，也就是227，用作散列地址；再比如关键字4321，其平方为18671041，抽取中间的3位，可以是671也可以是710用作散列地址。适合于不知道关键字的分布，而位数又不是很大的情况。

5.3.5、随机数法

选择一个随机数，取关键字的随机数作为它的散列地址，也就是： $H (k ey) = r an d o m (k ey)$ 这里的random是随机函数。当关键字的长度不等时，可采用这个方法。

5.4、处理冲突的方法

5.4.1、拉链法

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。
例如，关键字序列为 ${12,67,56,16,25,37,22,29,15,47,48,34\}$ ，用除留取余法构造散列函数 $H(key)=key\%12$ ，用拉链法处理冲突，建立的表如下图所示：
在这里插入图片描述

5.4.2、开放定址法

所谓的开放定址就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表够大，空的散列地址总能找到，并将记录存入。公式为： $H_{i}(key)=(f(key)+d_{i})\%m\ (d_{i}=1,2,3,...,m-1)$ 式中，H(key)为散列函数；i=0,1,2,…,k（k<=m-1）；m表示散列列表的表长； $d_{i}$ 为增量序列。
取定某一增量序列后，对应的处理方法就是确定的。

注意:在开放定址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记，进行逻辑删除。但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。

通常有以下4种方法：

1.线性探测法

当 $d_{i}=0,1,2,...,m-1$ 时，称为线性探测法。这种方法的特点就是：当发生冲突时，顺序查看表中下一个单元（探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找到一个空闲单元（表未满时，一定能找到空闲单元）或查遍全表。

（1）查找

在这里插入图片描述

（2）删除

在这里插入图片描述

（3）查找效率分析

在这里插入图片描述

（4）缺点

线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址，从而造成大量元素在相邻的散列地址上堆积，大大降低了查找效率。

2.平方探测法

当 $d_{i}=0^{2},1^{2},2^{2},...,k^{2},-k^{2}$ 时，称为平方探测法。其中k<m/2，散列表长度m必须是一个可以被表示为4k+3的素数，又称二次探测法。
平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

（1）查找

在这里插入图片描述

3.伪随机序列法

当 $d_{i}=伪随机数序列$ 时，称为伪随机序列法。

4.再散列法

当 $d_{i}=Hash_{2}(key)$ 时，称为再散列法，又称为双散列法。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数 $Hash_{2}(key)$ 计算该关键字的地址增量，它具体的散列函数形式如下： $H_{i}=(H(key)+i*Hash_{2}(key))\%m$ 初始探测地址 $H_{0}=H(key)$ ，i是冲突次数，初始为0。在再散列法中，最多经过m-1次探测就会遍历表中所有位置，回到 $H_{0}$ 位置。

5.4.3、公共溢出区法

这个方法其实就更加好理解，就是把凡是冲突的家伙额外找个公共场所待着。我们为所有冲突的关键字建立了一个公共的溢出区来存放。
就前面的例子而言，我们共有三个关键字37,48,34与之前的关键字位置有冲突，那么就将它们存储到溢出表中，如下图所示。
在这里插入图片描述
如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。