在数据结构中搜索：解释不同的搜索方法
已发表: 2021-05-03通讯网络在扩大，人们也在使用互联网！ 企业正在走向数字化以实现高效管理。 互联网上生成的数据正在增加，因此数据集变得越来越复杂。 仔细而有效地组织、管理、访问和分析数据是必不可少的，数据结构是最有用的技术，本文重点关注这一点！
目录
数据结构
在计算机科学中，数据结构是抽象数据类型 (ADT) 的基础，其中 ADT 是数据类型的逻辑形式。 数据类型的物理布局是使用数据结构实现的。 不同的数据结构类型用于不同类型的应用程序； 有些专门从事特定任务。
数据结构是数据值和它们之间的关系、适用于数据的操作和功能的集合。 它有助于以特定格式组织、管理和存储数据。 因此，用户可以轻松访问和有效地修改数据。
数据结构有助于管理大量数据，例如海量数据库。 高效的算法是建立在高效的数据结构之上的。 除了有效的存储之外，数据结构还负责从存储的内存中有效地检索信息。 它包括数组、链表、指针、搜索、堆栈、图形、队列、结构、程序、排序等。
本文介绍了在数据结构中搜索的概念及其方法。 详细解释了两个算法示例，以清楚地理解概念。 为了获得更多的知识、技能和专业知识，可以使用文章末尾提到的数据结构在线课程。
什么是数据结构中的搜索？
从以元素形式存储在计算机内存中的一组项目中查找所需信息的过程称为“在数据结构中搜索”。 这些项目集有多种形式，例如数组、树、图形或链表。 在数据结构中定义搜索的另一种方法是在项目集合中定位特定特征的所需元素。
搜索方法
数据结构中的搜索可以通过实现搜索算法来从任何形式的存储数据结构中检查或检索元素来完成。 这些算法根据其搜索操作的类型进行分类，例如：
- 顺序搜索
在检查集合的每个组件时，依次遍历数组或元素列表。
例如，线性搜索。
- 区间搜索
明确设计用于在排序数据结构中搜索的算法包含在区间搜索中。 这些算法的效率远远优于线性搜索算法。
例如，二分搜索、对数搜索。
这些方法是根据算法搜索与数据集合中的搜索项匹配的元素所花费的时间进行检查的，由下式给出，
- 最好的时间
- 平均时间
- 最坏情况时间
主要关注的是最坏情况时间，这会导致对算法性能的有保证的预测，并且与平均时间相比也很容易计算。
为了说明本文中的示例和概念，我们考虑了任何数据格式的数据集合中的“n”个项目。 显性操作用于简化分析和算法比较。 对于数据结构中的搜索，比较是一种主要操作，用 O() 表示，发音为“big-Oh”或“Oh”。
数据结构中有许多搜索算法，例如线性搜索、二进制搜索、插值搜索、跳转搜索、指数搜索、斐波那契搜索、子列表搜索、无处不在的二进制搜索、无界二进制搜索、子字符串搜索的递归函数和递归程序在给定数组中线性搜索元素。 本文仅限于线性和二进制搜索算法及其工作原理。
让我们详细了解数据结构中的线性搜索和二分搜索。
线性搜索
线性搜索算法按顺序搜索数组中的所有元素。 它的最佳执行时间是 1，而最差执行时间是 n，其中 n 是搜索数组中的项目总数。
它是数据结构中最简单的搜索算法，检查元素集合中的每一项，直到它与搜索元素匹配，直到数据收集结束。 当数据未排序时，首选线性搜索算法。
线性搜索有一些复杂性，如下所示：
- 空间复杂度
线性搜索的空间复杂度为 O(n)，因为它不使用任何额外空间，其中 n 是数组中元素的数量。
- 时间复杂度
*当搜索元素出现在搜索数组中的第一个元素时，最佳情况复杂度 = O(1)。
*当搜索元素不存在于元素集或数组中时，最坏情况复杂度 = O(n)。
*当元素出现在搜索数组中的某处时，指的是平均复杂度 = O(n)。
例子，
让我们采用如下所示的元素数组：
45、78、12、67、08、51、39、26
为了在上面给出的 8 个元素的数组中找到“51”，线性搜索算法将依次检查每个元素，直到其指针指向内存空间中的 51。 在数组中找到 51 需要 O(6) 时间。 要找到 12，在上面的数组中，它需要 O(3)，而对于 26，它需要 O(8) 时间。
二进制搜索
该算法通过比较数据集合中最中间的项目来查找特定项目。 当匹配发生时，它返回项目的索引。 当中间项大于该项时，它会搜索左子数组的中心项。 相反，如果中间项小于搜索项，则在右子数组中探索中间项。 它继续搜索一个项目，直到找到它或直到子数组大小变为零。
二分搜索需要对项目进行排序。 它比线性搜索算法快。 它的工作原理是分而治之。
运行时复杂度 = O(log n)
二分查找算法的复杂性如下：
- 最坏情况复杂度 = O (n log n)
- 平均复杂度 = O (n log n)
- 最佳情况复杂度 = O (1)
例子，
让我们采用 08 个元素的排序算法：
08、12、26、39、45、51、67、78
要在上述元素的数组中找到 51，
该算法会将一个数组分成两个数组，08、12、26、39和45、51、67、78
由于 51 大于 39，它将开始搜索数组右侧的元素。
它将进一步分为两个，例如 45、51 和 67、78
由于 51 小于 67，它将开始搜索该子数组的左侧。
该子数组再次分为两部分，分别为 45 和 51。
由于 51 是与搜索元素匹配的数字，因此它将返回其在数组中该元素的索引号。
它将得出结论，搜索元素51位于数组中的第6个位置。
由于比较计数比线性搜索算法显着减少，二分搜索将时间减少到一半。
阅读： Python 中的数据结构类型
插值搜索
它是二分搜索算法的改进变体，适用于搜索元素的探测位置。 与二分搜索算法类似，它仅在排序的数据集合上有效。
最差执行时间 = O(n)
当目标元素的位置在数据集合中已知时，将使用插值搜索。 要在电话簿中查找号码，如果要搜索莫妮卡的电话号码，可以直接探查名称以“M”开头的内存空间存储，而不是使用线性或二分法搜索。
结论
在数据结构中搜索是指在“n”个元素的数组中找到给定的元素。 有两类，即。 搜索中的顺序搜索和区间搜索。 几乎所有的搜索算法都基于这两个类别之一。 线性和二进制搜索是两种简单且易于实现的算法，其中二进制比线性算法工作得更快。
虽然线性搜索最直接，但它会检查每个元素，直到找到与搜索元素匹配的内容，因此在数据收集未正确排序时非常有效。 但是，如果数据集合是有序的并且数组的长度相当大，那么二进制搜索会更快。
在处理数据集时，数据结构是计算机编程的重要组成部分。 程序员和开发人员需要通过计算机编程技术的基础知识和更新不断更新和提升自己的技能。 处理数据结构的程序员应该经常选择课程。
如果您想了解有关数据科学的更多信息，请查看 IIIT-B 和 upGrad 的数据科学执行 PG 计划，该计划专为在职专业人士创建，提供 10 多个案例研究和项目、实用的实践研讨会、行业专家指导、与行业导师一对一，400 多个小时的学习和顶级公司的工作协助。
