线性搜索： 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） 停止。

为简单起见，我们以整数数组为例。线性搜索也适用于字符串、对象数组或结构体。

顺序搜索算法的伪代码

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 negative index is not valid
return -1

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(arr[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(arr, 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 代码示例线性搜索

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） 交换数据 [5] 和数据 [4]。然后数据数组将如下所示：

数据 [] = {1,5,9,8,4,7,3,11}

现在，如果你注意到，一个键被搜索的频率越高，索引就越低。因此，比较的次数也就越少。

移至最前：

在这个方法中，我们交换索引 0 处的搜索元素。因为如果再次搜索，我们可以在 O(1) 时间内找到它。

线性搜索算法的应用

以下是我们可以使用的一些线性搜索应用程序。

对于小型数组或列表中只有几个元素，使用线性搜索更容易。
线性搜索方法可以用于单个或多维数组或其他数据结构。
一般来说，线性搜索在“无序”数据中执行搜索简单而有效。我们可以轻松地从给定的无序列表中获取单个数据。