线性搜索算法简介：简介与特点[附示例]

什么是搜索？

搜索是在元素列表中查找给定元素的过程。 它有助于搜索特定记录。 因此，它是一种识别给定项目位置的技术。 搜索过程的成功取决于要搜索的项目是否已被识别。

数据结构允许通过两种方法搜索数据。

1. 线性搜索或顺序搜索
2. 二进制搜索

线性搜索

线性搜索算法是一种用于数据顺序搜索的算法。 该算法找到具有 O(n) 复杂度的给定元素。 它应用于项目集合。 数据的每一项都按顺序搜索，如果与搜索到的元素匹配则返回。 如果未找到匹配项，则继续搜索，直到收集的数据结束。 它基本上是一种在遍历列表时探索每个元素的技术。 搜索算法可以应用于已排序和未排序的数据。 实际上线性搜索很少使用，因为其他搜索算法（如二进制搜索算法和哈希表）提供了更快的搜索选项。

线性搜索算法的步骤

• 用户对搜索元素的阅读。
• 要搜索的元素与列表的第一个元素一起压缩。
• 如果元素匹配，则生成返回。
• 如果元素不匹配，则将要搜索的元素与列表的第二个元素进行比较。
• 重复该过程，直到元素匹配为止。

线性搜索算法的特点

1. 它通常应用于一小部分未排序或无序的数据。
2. 时间线性依赖于元素的数量，因此如果 O(n) 则具有时间复杂度。
3. 实现非常简单。

线性搜索算法

一个连续的循环方法继续进行，除非并且直到找到该项目

• 算法 Seqnl_Search(list, item)
• 前：列表！=；
• Post：如果找到则返回该项目的索引，否则：1
• 索引 <- fi
• while index < list.Cnt and list[index] != item //cnt: 计数器变量
• 索引 <- 索引 + 1
• 结束时
• 如果 index < list.Cnt 并且 list[index] = item
• 回报指数
• 万一
• 回报：1
• 结束 Seqnl_Search

线性搜索示例

问题：给定一个包含 n 个元素的数组 arr[]，编写一个函数来搜索 arr[] 中的给定元素 x。

图 1：显示线性搜索算法实现的代码示例

资源

线性搜索算法可用于多种编程语言。

1. Python中的线性搜索

图 2：以 Python 语言显示线性搜索算法的代码示例

资源

输出：元素存在于索引 3

2. C中的线性搜索

图 3：显示 C 语言线性搜索算法的代码示例

资源

输出：元素存在于索引 3

3. 数据结构中的线性搜索

数据结构中线性搜索问题的伪代码是

图 4：线性搜索算法的伪代码

资源

二进制搜索

二进制搜索是一种在元素数组中搜索元素的算法。 与线性搜索算法相比，二分搜索算法适用于数据的排序列表。

二分查找算法包括以下步骤

• 将要搜索的元素与列表或数组中间的元素进行比较。
• 如果元素与列表中的元素匹配，则返回中间元素的索引。
• 如果没有返回匹配，则检查该元素是否大于或小于中间的元素。
• 对于值大于中间元素的元素，在数组的右侧进行搜索。
• 类似地，如果元素的值小于中间元素，则搜索将继续到列表的左侧。

因此，当数据以排序方式包含大量棒元素时，最好应用二进制搜索。 这使得搜索算法必须对列表/数组进行排序。

二分查找的特点

• 二进制搜索算法对于搜索数组中的大量元素很有用。
• 二分查找算法的时间复杂度为 O(logn)。
• 二分搜索算法的实现很简单。

二分搜索算法

• 算法 Binary_Search(list, item)
• 将 L 设置为 0，将 R 设置为 n：1
• 如果 L > R，则 Binary_Search 因不成功而终止
• 别的
• 将 m（中间元素中的位置）设置为 (L + R) / 2 的底
• 如果 Am < T，将 L 设置为 m + 1 并转到步骤 3
• 如果 Am > T，将 R 设置为 m: 1 并转到步骤 3
• 现在，Am = T，
• 搜索完成； 返回（米）

结论

在本文中，我们研究了什么是线性搜索算法，并详细研究了如何使用线性搜索算法从列表中搜索某个元素。 最后，我们还看到了如何使用 Python 3 作为语言实际实现线性搜索算法并获得我们想要的输出。

如果您对数据科学感兴趣，您必须查看 IIIT-B 和 upGrad 的数据科学执行 PG 计划，该计划专为在职专业人士精心打造，并提供大量案例研究、实践研讨会、一对一指导，以及多得多。