迹忆客 专注技术分享

线性搜索是最简单的搜索算法。它也被称为顺序搜索，因为在这种算法中，我们通过遍历整个数组并将每个元素与所需的项目进行比较来寻找匹配的元素。如果找到了所需的元素，则返回索引或该元素；否则，我们继续搜索，直到用尽数组。我们也可以在一个数组中寻找一个项目的多次出现。它主要用于在一个未排序的数组中搜索项目。由于它比二叉搜索慢得多，所以实际上并不使用。

线性搜索算法

假设我们有一个未排序的数组 A[]，包含 n 个元素，我们想找到一个元素-X。

• 使用 for 循环从最左边的元素开始遍历数组中的所有元素，并执行以下操作。
  • 如果 A[i] 的值与 X 相匹配，则返回索引 i(如果可能有多个元素与 X 相匹配，则不返回索引 i，而是打印所有索引或将所有索引存储在一个数组中并返回该数组。)
  • 否则继续下一个元素。
  • 如果已在数组的最后一个元素，退出 for 循环。
• 如果没有一个元素匹配，则返回 -1。

线性搜索示例

假设我们有数组：(5, 3, 4, 2, 1, 6)。

• 情况 1：我们要寻找 X=5。

第一个元素本身是匹配的，我们返回索引 0。(最佳情况)

• 情况 2：我们想寻找 X=1。

我们遍历数组并到达索引 4，找到一个匹配的索引并返回该索引。(平均情况)

• 情况 3：我们要寻找 X=9。

我们遍历数组，但当我们到达数组的最后一个元素时，没有找到匹配的元素。我们返回 -1。(最坏情况)

线性搜索算法的实现

单一匹配的线性搜索算法

#include <iostream>
using namespace std;

int search(int arr[], int n, int x) {
    // Traverse the array sequentially
    for (int i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}

int main() {
    int n = 5;
    int arr[] = {2, 4, 0, 1, 9};
    int x = 1;
    int result = search(arr, n, x);
    if (result == -1) cout << "Element not found";
    else cout << "Element found at index: " << result;
}

多重匹配的线性搜索算法

#include <bits/stdc++.h>
using namespace std;

vector<int> search(int arr[], int n, int x) {
    vector<int>ans;
    // Traverse the array sequentially
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) {
            ans.push_back(i);
        }
    }
    return ans;
}

int main() {
    int n = 9;
    int arr[] = {2, 4, 0, 1, 9, 2, 1, 2, 1};
    int x = 1;
    vector<int> res = search(arr, n, x);
    if (res.empty()) {
        cout << "Element not found!!";
    }
    else {
        cout << "Element found at ";
        for (int i = 0; i < res.size(); i++) {
            cout << res[i] << " ";
        }
    }
}

线性搜索算法的复杂度

时间复杂度

• 平均情况

线性搜索算法的时间复杂度为 O(n)。

• 最佳情况

最佳情况下的时间复杂度是 O(1)。当要搜索的元素是数组中的第一个元素时，就会出现这种情况。

• 最坏情况

最坏的情况是，我们要搜索的元素不在数组内，或者在数组的最后一个索引处。最坏情况下的时间复杂度是 O(n)。

空间复杂度

该算法的空间复杂度取决于匹配的数量和使用的实现。一般来说，空间复杂度为 O(1)，但如果在一个数组中存储多个匹配索引，空间复杂度可能更高。