极客干货|首先看一下数组和链表原理的检索本质

作者|极客时间陈东

来源|极客时间“检索技术核心20讲”

人们经常说搜索不只是搜索. 你看，这还不是很清楚. 检索技术实际上涵盖了常用数据结构的检索，大数据检索，搜索引擎，推荐引擎等.

在日常工作或面试中，我们经常遇到一些与查询相关的问题，例如:

这些是检索技术. 今天，我将向您推荐“检索技术核心20讲义”课程的第一部分: 乍一看从数组和链表原理中进行检索的本质.

以下是全文.

———————————————————————————————————————————————— ———

你好，我是陈东. 欢迎来到本专栏的第一部分. 今天，我们主要讨论如何检索线性结构（如数组和链表）. 我希望通过这一讨论过程，您可以对什么是检索有一个深刻的了解.

您可以首先考虑一个问题: 什么是检索？从字面上看，检索实际上是一种从数据存储位置有效地提取我们所需信息的技术. 因此，检索效率与数据存储方法密切相关. 具体而言，不同的存储方法将导致不同的检索效率. 然后，有必要研究数据结构的存储特性对检索效率的影响.

因此，今天，我们将从数组和链表的存储特征开始. 首先让我们看一下如何检索它们.

我相信您已经熟悉数组的特性，即使用连续的内存空间来存储数据. 如果我无法申请连续的存储空间怎么办？此时，链接列表可以派上用场. 链接列表可以申请不连续的空格. 这些空间由指针按顺序连接以形成链，这就是链表获得其名称的原因. 但是，严格来说，这称为单链表. 如果没有特殊说明，我下面提到的链表是指只有一个后续指针的单个链表.

从图中可以看出，数组和链表分别代表连续空间和不连续空间的最基本存储方法. 它们是线性列表的典型代表. 所有其他数据结构，例如堆栈，队列，二叉树和B +树，无非就是两者的组合和更改. 以堆栈为例，它本质上是一个读写位置受限制的数组，其特点是只允许后进先出.

因此，我们只需要从最基本的数组和链表开始，并根据实际应用中遇到的问题考虑解决方案，就可以逐渐学习和理解更多的数据结构和检索技术.

那么，两个线性数据结构，数组和链表的检索效率如何？让我们仔细看看.

首先，如果数据存储顺序混乱，无论是数组还是链表，则要查找是否存在指定的元素. 在没有数据分发信息的情况下，我们只能从头到尾遍历才能知道它是否存在. 这样的检索效率是O（n）. 当然，如果数据集不大，则足以直接遍历. 但是，如果数据集很大，则需要考虑更有效的检索方法.

对于大型数据集，我们通常先通过排序算法将其转换为有序数据集，然后再使用诸如二进制搜索算法之类的某些检索算法来完成有效的检索.

二元搜索也称为半搜索，其思想非常直观，即将有序数组分为两部分，仅在半侧搜索即可提高搜索效率. 二进制搜索如何工作？让我们看一下具体的实现步骤.

我们将首先从中间元素进行检查，该元素将具有三种查询结果.

首先是中间元素的值等于我们要查询的值. 也就是说，如果找到它，直接返回即可.

如果中间元素的值小于我们要查询的值，那么下一步如何检查？这是第二种情况. 数组是有序的，因此我们使用中间元素作为分隔符. 数组元素的左半部分必须小于中间元素，该中间元素小于我们要查询的值. 因此，我们要查询的值只能存在于数组的右半部分.

对于数组的右半部分，我们仍然可以继续使用二进制搜索的想法，然后从它的中间开始并重复上述过程. 这样，“二分法”不断下降，每次搜索空间可以减少一半. 整体平均查询效率为O（log n），远低于遍历整个数组O（n）的成本.

二进制搜索图标

类似地，对于第三种情况，如果中间元素的值大于我们要查询的值，那么我们只能在左侧查找数组元素.

由此可见，适当组织数据存储可以提高检索效率. 检索的核心思想实际上是通过合理地组织数据来尽可能快地减小查询范围. 在本专栏的后续章节中，我们将看到更多的搜索算法和技术. 实际上，它们的本质是通过灵活地运用各种数据结构的特征来组织数据，从而快速缩小查询范围.

正如我们之前所说，如果数据存储不正确，则链表的检索效率将非常低. 然后无序链表的快速查找，您可能不得不问，看来有序链表不能提高检索效率. 为什么？您可以停下来自己想一想，然后在下面阅读我的解释.

阵列的“连续空间存储”具有随机访问的特征. 将二进制搜索应用于有序数组时，它可以直接花费O（1）的时间来访问中间的值，然后将中间的值用作分界线，仅选择向左或向右继续搜索，可以迅速缩小查询范围.

链接列表不具有“随机访问”功能. 当链表要访问中间元素时，我们必须从链表的开头开始并逐步遍历链，以访问所需的值. 如果要访问中间节点，则需要遍历一半的节点，时间成本已经是O（n / 2）. 从这个角度来看，由于缺少“随机访问位置”功能，因此链表的检索能力较弱.

但是，所有内容都有两个方面，并且链接列表的搜索能力很弱. 作为补偿，动态调整会更容易. 我们可以以O（1）为代价完成节点的插入和删除，这对于“连续空间”数组来说很困难. 毕竟，如果要在有序数组中插入一个元素，以确保“有序数组”，我们需要将数组中该元素后面的元素移位，所有顺序都后移一个，即实际上是O（n）时间成本.

在有序数组和链表中插入新元素的操作和时间成本的比较

因此，在某些需要频繁插入和删除数据的情况下，有序数组可能不是最合适的选择. 另一方面无序链表的快速查找，在数据量非常大的情况下，我们几乎不能保证可以申请连续空间来构建有序数组. 因此，学会合理有效地使用链表也很重要.

从本质上讲，我们正在学习一个链表，即，学习“非连续存储空间”的组织方案. 我们知道，对于“不连续空间”，我们可以使用指针将其连接为一个整体. 只要我们掌握了这个想法，就可以在不同的应用场景中设计合适的数据结构，而不受链表本身的结构限制的约束.

我们可以看一个简单的转换示例.

例如，如果我们觉得链表的逐节点遍历太慢，那么我们可以对其做一个简单的修改吗？掌握了链表的核心思想之后，我们可以轻松想到一个改进计划，即让链表的每个节点不仅存储一个元素，而且存储一个小数组. 这样，我们可以大大减少节点的数量，从而减少由于顺序遍历这些节点而导致的“低寻址效率”.

例如，我的链表只有两个节点，每个节点存储一个小的有序数组. 这样，在搜索时，我可以使用二进制搜索的思想首先查询存储在第一个节点中的小数组的最后一个元素，以查看它是否是我们要查询的数字. 如果没有，我们将继续在第一个节点中存储的小型数组中进行二进制搜索；否则，我们将继续执行二进制搜索. 或继续在第二个节点中存储的小型数组中执行二进制搜索. 这种结构可以同时考虑数组和链表的特性，并且时间成本也为O（log n）.

改良的链表

可以看出，尽管常规链表只能被遍历和检索，但只要我们掌握“可以灵活调整非连续存储空间”的特征，我们就可以设计出更有效的数据结构和检索算法.

好的，本次讲座的内容几乎相同. 让我们回顾一下本讲座的主要内容: 以数组和链表表示的线性结构的检索技术和效率分析.

首先，我们学习了特定的检索方法. 对于无序数组，我们可以遍历检索. 对于有序数组，我们可以使用二进制搜索. 链表具有灵活的调整功能，适合经常修改数据的场合.

第二，您还应该开始实现一些检索的核心思想: 合理地组织数据，尽快缩小查询范围并提高检索效率.

今天的内容实际上并不难，所涉及的核心思想也非常简单，但是对于我们来说，掌握检索技术非常重要. 您必须了解得很好.

随着课程的深入，我们将逐步解锁更先进的检索技术和复杂系统，但是核心思想与我们今天所学的知识密不可分.

因此，从最基本的数组和链表开始，然后考虑基于特定问题的解决方案，这可以帮助您逐步构建知识系统，从而更好地掌握检索原理并提高代码效率. 旨在提高系统设计能力.

结合您今天学习的数组和链表的检索技术和效率分析，您可以考虑这两个问题.

为了有效地检索有序数组，为什么我们使用二进制搜索算法而不是3-7搜索算法或4-6搜索算法？对于单个查询值k，我们已经熟悉如何使用二进制搜索. 给定两个查询值x和y作为查询范围，如果要在有序数组中查找x和y之间的所有元素怎么办？

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-176153-1.html