线性搜索： Python, C++ 例如：
陈莎拉
什么是搜索算法？
搜索算法旨在根据给定的数据结构，从一组元素或对象中查找特定元素或对象。例如，从给定的高度列表中查找最小高度，或者从数字列表或数组中查找最高分。一些常用的搜索算法包括“线性搜索”、“二分搜索”、“跳跃搜索”、“斐波那契搜索”等。
什么是线性搜索？
线性搜寻 线性搜索是最简单的搜索算法之一。它从给定的列表或数组中逐个查找指定的元素。线性搜索遍历整个列表，检查是否存在与搜索元素相等的特定元素。它也被称为…… 顺序搜索.
线性搜索函数有什么作用？
整数数组表示为“Numbers”，变量“item”包含要搜索的整数。
现在，线性搜索算法可以提供以下输出：
- “-1”表示数组中未找到给定的元素。
- 0 到 n-1 之间的任意数字；表示找到搜索元素，并返回该元素在数组上的索引。其中，“n”表示数组的大小。
线性搜索如何工作？
假设我们有一个包含整数的数组。任务是在数组中找到给定的数字。
- 如果数字位于数组中，我们需要返回该数字的索引。
- 如果未找到给定的数字，则它将返回 -1。
流程图中，“Data”是整型数组，“N”是数组的大小，“item”是我们想要在数组中搜索的数字。
线性搜索算法流程图：
流程图的步骤如下：
步骤1） 阅读搜索项目“item”。
步骤2） 初始化 i=0 和 index=-1。
步骤3） 如果我
步骤4） 如果 Data[i] 等于 “item”，则转到步骤 5。否则转到步骤 6。
步骤5） 索引 = i（因为该项目位于索引 i 处）。转到步骤 8。
步骤6） i=i+1。
步骤7） 转到步骤3。
步骤8） 停止。
为简单起见，我们以整数数组为例。线性搜索也适用于字符串、对象数组或结构体。
昵称 Code 顺序搜索算法
以下伪代码描述了上述线性搜索的逻辑。它从数组的第一个索引开始遍历，如果找到匹配项则返回其位置，否则返回 -1。
function linearSearch: in → Data[], item foundAt = -1 for i in (0 to data.length): if data[i] equals item: // item is found in the array // returning the index return i // item not found in the array // -1 means no item found, as a negative index is not valid return -1
C++ Code 线性搜索示例
以下是完整的 C++ 实现顺序搜索并打印搜索值的索引的程序。
#include <bits/stdc++.h> using namespace std; int linearSearch(int *arr, int item, int n) { int idx = -1; for (int i = 0; i < n; i++) { if (arr[i] == item) { idx = i; break; } } return idx; } int main() { int array[] = {1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10}; int n = sizeof(array) / sizeof(array[0]); int item; cout << "Enter a number to search: "; cin >> item; int idx = linearSearch(array, item, n); if (idx >= 0) { cout << item << " is found at index " << idx << endl; } else { cout << "Could not find " << item << " in the array" << endl; } }
输出：
Enter a number to search: -10 -10 is found at index 14
Python Code 线性搜索示例
同样的逻辑 Python 使用单个循环遍历列表索引，并返回匹配元素的位置。
def linearSearch(data, item): for i in range(len(data)): if data[i] == item: return i return -1 data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10] item = int(input("Enter a number to search: ")) idx = linearSearch(data, item) if idx >= 0: print("{} is found at index {}".format(item, idx)) else: print("{} was not found".format(item))
输出：
Enter a number to search: -10 -10 is found at index 14
线性搜索算法的复杂度分析
通常，时间复杂度指的是完成特定任务所需的CPU时间。在线性搜索算法中，任务是从数组元素中找到搜索键。
三种类型的时间复杂度为：
- 最坏的情况下
- 最佳案例情景
- 平均情况
最坏情况下线性搜索的时间复杂度：
假设我们需要在一个大小为“n”的数组中执行线性搜索。我们可以在索引 0 到 n-1 之间找到搜索项。在最坏的情况下，算法会尝试将数组中的所有元素与搜索元素进行匹配。
在这种情况下，最坏情况下的复杂度为 O(n)。这里的“O”——大 O 符号——表示复杂度函数。
最佳情况下线性搜索的时间复杂度：
假设我们要查找数组中位于第一个位置的元素。在这种情况下，线性搜索算法不会搜索数组中的所有 n 个元素。因此，其复杂度为 O(1)，即常数时间。
平均情况下线性搜索的时间复杂度：
当在数组的中间索引处找到一个元素时，可以说线性搜索的平均情况复杂度为 O(N)，其中 N 表示数组的长度。
线性搜索算法的空间复杂度：
线性搜索的空间复杂度始终为 O(N)，因为线性搜索函数中不需要存储或使用任何类型的临时变量。
如何改进线性搜索算法
在程序的整个生命周期中，搜索可以执行多次。我们也有可能运行线性搜索算法，并多次搜索某个特定的键。我们可以使用“二分查找算法“如果数组是已排序数组。
假设数组由 10 万个数字组成，并且目标元素位于第 5000 个索引处。因此，算法将尝试比较 5000 个元素。现在，比较是 CPU 密集型任务。为了优化线性搜索算法，我们有两个选择。
- 换位
- 移到前面
换位：
在这种方法中，我们将搜索元素与其在数组中的前一个元素交换位置。例如，假设你有一个如下所示的数组：
数据[] = {1,5,9,8,7,3,4,11}
现在，我们要搜索4.转置的步骤：
步骤1） 在索引 4 处找到“6”。进行了六次比较。
步骤2） 交换 data[6] 和 data[5]。然后数据数组将如下所示：
数据[] = {1,5,9,8,7,4,3,11}
步骤3） 再次搜索 4。在索引 5 处找到。这次进行了五次比较。
步骤4） 交换 data[5] 和 data[4]。然后 data 数组将如下所示：
数据[] = {1,5,9,8,4,7,3,11}
现在，如果你仔细观察，就会发现，某个键被搜索的频率越高，其索引就越小，从而减少了比较次数。
移至最前：
在这种方法中，我们将搜索元素交换到索引 0。因为如果再次搜索该元素，我们可以在 O(1) 时间内找到它。
线性搜索算法的应用
以下是我们可以使用的一些线性搜索应用程序。
- 对于小型数组或列表中只有少量元素的情况，使用线性搜索更容易。
- 线性搜索方法可以用于单个或 多维数组 或其他数据结构。
- 一般来说，线性搜索在“无序”数据中执行搜索简单而有效。我们可以轻松地从给定的无序列表中获取单个数据。
