数据结构检索（查找）之入土攻略（一）
目录
1 检索的基本概念
度娘作为中国最牛的中文搜索引擎，各种问题在其中都会找到答案，其中不乏一些辣眼的奇葩提问。
不好意思，以上在扯犊子。
搜索引擎是检索的典型应用，当我们在搜索引擎上输入一个关键字，点击“搜索”按钮时，搜索引擎会带着关键字奔向索引数据库，检索到所有包含搜索词的网页，并依据它们的浏览次数与关联性等一系列算法确定网页级别，排列出顺序，最终以网页的形式显示给用户。
检索（查找）：在一组记录集合中找到关键码值等于给定值的某个记录，或者找到关键码值符合特定条件的某些记录的过程。
提高检索效率的方法：
- 预排序
- 建立索引（关于索引的学习，移步：https://blog.****.net/wydyd110/article/details/81904483）
- 散列技术
- 对于基于磁盘的应用程序，可选择B系列树方法
2 线性表的检索
2.1 顺序检索
（来源于《大话数据结构》）
上述图书尽管已经排列整齐，但还没有分类，因此我们要找书，只能从头到尾从尾到头一本一本地查看，直到找到或全部查找完为止。这就是顺序检索。
顺序检索：针对线性表里的所有记录，逐个进行关键码和给定值的比较。
–若某个记录的关键码和给定值比较相等，则检索成功
–否则检索失败(找遍了仍找不到)
查找成功：最好的情况就是在第一个位置就找到了，比较1次，时间复杂度为O(1)，最坏的情况是在最后一位才找到，需要比较n次，时间复杂度为O(n)
ASL = （1 + 2 + ......+ n） = (1+n)n/2n = (1+n)/2
查找失败：需要比较n+1次（设置了一个监视哨）
ASL = (n+1)n/n = n+1
（p取1或0）
顺序检索的优缺点：
优点：插入元素可以直接加在表尾 Θ(1)
缺点：检索时间太长 Θ(n)
2.2 二分检索
将上述图书排列整齐后，还按照书名拼音的首字母排序放置，也就是对图书做了有序排列，这样利于查找。
二分检索（折半查找）：元素必须是有序的，必须采用顺序存储。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若小于中间结点的关键字，则在中间结点的左半区继续查找；若大于中间结点的关键字，则在中间结点的右半区继续查找。
折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
2.3 分块检索
分块检索原理与稀疏索引（分块索引）类似，可参考
《数据结构索引之杀死攻略（一）》：https://blog.****.net/wydyd110/article/details/81904483
分块检索的优缺点：
优点：插入删除相对容易，没有大量记录移动
缺点：增加一个辅助数组的存储空间
– 初始线性表分块排序
– 当大量插入/删除时，或结点分布不均匀时，速度下降
3 集合的检索
集合（set）：由若干个确定的、相异的对象（element）构成的整体
集合的检索：确定一个值是不是某个集合的元素
集合的检索的原理与位图索引类似，可参考：
《数据结构索引之杀死攻略（三）》：https://blog.****.net/wydyd110/article/details/82012960
仿佛检索的知识点到此就结束了，然而
下面跳转至《数据结构检索（查找）之入土攻略（二）》：https://blog.****.net/wydyd110/article/details/82144549