迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 算法 >

线性搜索

作者:迹忆客 最近更新:2023/03/26 浏览次数:

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

线性搜索算法

假设我们有一个未排序的数组 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),但如果在一个数组中存储多个匹配索引,空间复杂度可能更高。

上一篇:指数搜索

下一篇:Tim 排序

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

将二叉树转换为二叉搜索树

发布时间:2023/03/20 浏览次数:159 分类:算法

本教程教大家如何将二叉树转换为二叉搜索树。二叉树是一种非线性数据结构。它被称为二叉树,因为每个节点最多有两个子节点。这些子节点被称为左子和右子。

二叉搜索树删除

发布时间:2023/03/20 浏览次数:164 分类:算法

本教程介绍了二叉搜索树的删除操作。

二叉搜索树检查

发布时间:2023/03/20 浏览次数:151 分类:算法

如何检查给定的二叉树是否是二叉搜索树。

二叉搜索树

发布时间:2023/03/20 浏览次数:105 分类:算法

本教程介绍了数据结构 Binary Search Tree。

二叉树遍历

发布时间:2023/03/20 浏览次数:202 分类:算法

本教程介绍了二叉树上的树遍历中序遍历、前序遍历和后序遍历。

循环双向链表

发布时间:2023/03/20 浏览次数:143 分类:算法

本教程介绍了循环双向链表的数据结构。

循环链接列表

发布时间:2023/03/20 浏览次数:188 分类:算法

本教程介绍了循环链接列表的数据结构。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便