数据结构检索（查找）之入土攻略（一）

女爷i 2022-05-15 08:16 253阅读 0赞

**目录**

1 检索的基本概念

2 线性表的检索

2.1 顺序检索

2.2 二分检索

2.3 分块检索

3 集合的检索

--------------------

# 1 检索的基本概念 #

度娘作为中国最牛的中文搜索引擎，各种问题在其中都会找到答案，其中不乏一些辣眼的奇葩提问。

![70][]

![70 1][]

不好意思，以上在扯犊子。

![70 2][]

搜索引擎是检索的典型应用，当我们在搜索引擎上输入一个关键字，点击“搜索”按钮时，搜索引擎会带着关键字奔向索引数据库，检索到所有包含搜索词的网页，并依据它们的浏览次数与关联性等一系列算法确定网页级别，排列出顺序，最终以网页的形式显示给用户。

**检索（查找）**：在一组记录集合中找到关键码值等于给定值的某个记录，或者找到关键码值符合特定条件的某些记录的过程。

> **提高检索效率的方法：**
> 
>  *  预排序
>  *  建立索引（关于索引的学习，移步：[https://blog.csdn.net/wydyd110/article/details/81904483][https_blog.csdn.net_wydyd110_article_details_81904483]）
>  *  散列技术
>  *  对于基于磁盘的应用程序，可选择B系列树方法

# 2 线性表的检索 #

**平均查找长度：**在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度是所有查找过程中进行关键字的比较次数的平均值。

![20181203135437770.png][]

![20181203135522636.png][]

## 2.1 顺序检索 ##

![70 3][]

（来源于《大话数据结构》）

上述图书尽管已经排列整齐，但还没有分类，因此我们要找书，只能从头到尾从尾到头一本一本地查看，直到找到或全部查找完为止。这就是顺序检索。

> **顺序检索：**针对线性表里的所有记录，逐个进行关键码和给定值的比较。  
> –若某个记录的关键码和给定值比较相等，则检索成功  
> –否则检索失败(找遍了仍找不到)

![70 4][]

**查找成功：**最好的情况就是在第一个位置就找到了，比较1次，时间复杂度为O(1)，最坏的情况是在最后一位才找到，需要比较n次，时间复杂度为O(n)

ASL = （1 + 2 + ......+ n）\* 1/n = (1+n)n/2n = (1+n)/2

**查找失败：**需要比较n+1次（设置了一个监视哨）

ASL = (n+1)n \* 1/n = n+1

![70 5][]

（p取1或0）

> **顺序检索的优缺点：**
> 
> **优点：**插入元素可以直接加在表尾 Θ(1)
> 
> **缺点：**检索时间太长 Θ(n)

## 2.2 二分检索 ##

## ![70 3][] ##

将上述图书排列整齐后，还按照书名拼音的首字母排序放置，也就是对图书做了有序排列，这样利于查找。

**二分检索（折半查找）：**元素必须是有序的，必须采用顺序存储。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若小于中间结点的关键字，则在中间结点的左半区继续查找；若大于中间结点的关键字，则在中间结点的右半区继续查找。

![70 6][]

**判定树**

二分查找的过程可用二叉树来描述，圆中的值表示一个记录的关键字值，树中最下面的叶结点均为方形。表示查找不成功的情况。

**栗子**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70][]

树高=4，等概率情况下

查找成功ASL = （1\*1 + 2\*2 + 3\*3 + 4\*4）/11=3

查找失败ASL = （3\*4 + 4\*8）/12 = 11/3

> 查找给定值的比较次数不超过树的高度。等概率查找时，查找成功的平均查找长度为：
> 
> ![20181203140549710.png][]

![70 7][]

> 折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

## 2.3 分块检索 ##

分块检索原理与稀疏索引（分块索引）类似，可参考

《数据结构索引之杀死攻略（一）》：[https://blog.csdn.net/wydyd110/article/details/81904483][https_blog.csdn.net_wydyd110_article_details_81904483]

![70 8][]

![70 9][]

> **分块检索性能分析：**
> 
> 设线性表中共有 n 个数据元素，将表分成 b 块，每块有s个记录。
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 1][]
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 2][]

> **分块检索的优缺点：**
> 
> **优点：**插入删除相对容易，没有大量记录移动
> 
> **缺点：**增加一个辅助数组的存储空间  
> – 初始线性表分块排序  
> – 当大量插入/删除时，或结点分布不均匀时，速度下降

# 3 集合的检索 #

**集合（set）：**由若干个确定的、相异的对象（element）构成的整体  
**集合的检索：**确定一个值是不是某个集合的元素

集合的检索的原理与位图索引类似，可参考：

《数据结构索引之杀死攻略（三）》：[https://blog.csdn.net/wydyd110/article/details/82012960][https_blog.csdn.net_wydyd110_article_details_82012960]

![70 10][]

![70 11][]

仿佛检索的知识点到此就结束了，然而

![70 12][]

下面跳转至《数据结构检索（查找）之入土攻略（二）》：[https://blog.csdn.net/wydyd110/article/details/82144549][https_blog.csdn.net_wydyd110_article_details_82144549]

[70]: /images/20220515/755e31ea1fdf44788ec8ec3982550b7d.png
[70 1]: /images/20220515/4424538fd78c4c7296b86d1dd76a588a.png
[70 2]: /images/20220515/5ba0486e734243df926511db097359ad.png
[https_blog.csdn.net_wydyd110_article_details_81904483]: https://blog.csdn.net/wydyd110/article/details/81904483
[20181203135437770.png]: /images/20220515/43e8ee1e01e84618a4b1ff1771aa14a5.png
[20181203135522636.png]: /images/20220515/ad02e736dd09412f9f81805f7dcea8df.png
[70 3]: /images/20220515/b108fe73cf664e8191237c43dc99c291.png
[70 4]: /images/20220515/d4e00e401a6c41efb561d1119ff2e50d.png
[70 5]: /images/20220515/f3e5dbaecc7345d8a374b76050491df2.png
[70 6]: /images/20220515/321406c92de34d1185d34fe50cc5dabc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70]: /images/20220515/5afb2ed6297e4196a629663e24e7e94c.png
[20181203140549710.png]: /images/20220515/6bcf9b7ba0034528b54c763d2a7b719f.png
[70 7]: /images/20220515/f9f03856915748e9aba5cd0c0ac4b440.png
[70 8]: /images/20220515/59d14ffc83194978ac0514025b3a566c.png
[70 9]: /images/20220515/b599933dc92e464ea69689de00cb22c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 1]: /images/20220515/6428fa721e064aca8577cf8c1f4ceaf5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70 2]: /images/20220515/101aac6ed38142ed8442b2ba727c651a.png
[https_blog.csdn.net_wydyd110_article_details_82012960]: https://blog.csdn.net/wydyd110/article/details/82012960
[70 10]: /images/20220515/d9443d6a4ff247aab50af8b65b84f1ad.png
[70 11]: /images/20220515/b7e430a0ea6c44b8973aa4e3a1956119.png
[70 12]: /images/20220515/90e67a9d2ac441e89c69e037ca15850a.png
[https_blog.csdn.net_wydyd110_article_details_82144549]: https://blog.csdn.net/wydyd110/article/details/82144549