C++ 线性搜索算法

2024 年 8 月 28 日 | 阅读 17 分钟

引言

算法在计算机科学和编程中起着至关重要的作用，因为它们使我们能够高效且有效地解决各种问题。线性查找算法就是其中一种算法，它是一种简单但至关重要的查找算法，可以帮助我们在数据集合中查找特定元素。在本文中，我们将深入探讨 C++ 中的线性查找算法、其原理以及如何实现它。

什么是线性查找？

线性查找，也称为顺序查找，是一种在列表或数组中查找特定元素的简单算法。它遵循一种简单直观的方法，即逐个检查数据结构中的每个元素，直到找到所需的元素或到达数据结构的末尾。

演变

早期计算机科学：线性查找的根源在于计算机编程的早期。在 20 世纪中叶，当计算机尚处于起步阶段时，程序员需要一种简单的方法来定位数据集中的特定数据。线性查找是一种自然而直接的方法。
手动卡片排序：在电子计算机出现之前，线性查找就已用于手动数据处理。例如，在图书馆和行政任务中，卡片目录是手动排序的，个人会依次搜索这些卡片以查找特定信息。
早期编程语言：随着编程语言的发展，线性查找成为计算机编程的基本组成部分。Fortran 和 COBOL 等早期编程语言依赖线性查找进行数据检索和处理。
教科书算法：线性查找通常包含在教科书中和教育材料中，以向学生介绍编程概念。它作为算法的一个简单而实用的例子。
对算法设计的影响：线性查找的概念影响了更高级查找算法的发展。计算机科学家和程序员在构建线性查找原理的基础上，创建了更有效的算法，例如利用排序数据的二分查找。
在软件开发中的持久性：虽然线性查找对于大型数据集来说并不总是最高效的选择，但它在软件开发中仍然占有一席之地。它被用于各种应用中，在这些应用中，简单性、易于实现性和数据结构限制使其成为一个实用的选择。
教育和学习：线性查找仍然是计算机科学教育中的一个基本概念。它通常是学生遇到的第一个查找算法，帮助他们建立算法设计和解决问题的基础。
现实世界应用：线性查找仍在使用，尤其是在处理小型数据集或在其他算法可能不是必需的情况下。它被用于查找列表、数据库和简单数据结构中的元素等任务。

线性查找的关键特性

简单性：线性查找是最简单的查找算法之一。它易于理解和实现，使其成为小型数据集的合适选择。
无序数据：线性查找在有序和无序数据上都能很好地工作，因为它单独检查每个元素。
时间复杂度：线性查找的时间复杂度为 O(n)，其中“n”表示数据集中元素的数量。这意味着在最坏的情况下，算法可能需要扫描所有元素。
无数据操作：与某些查找算法不同，线性查找不需要在执行查找之前对数据进行排序或以任何方式进行操作。

时间和空间复杂度

线性查找的时间复杂度

线性查找算法的时间复杂度为 O(n)，其中“n”表示正在搜索的数据集中元素的数量。在进行线性查找时，算法会依次扫描数据，将每个元素与目标值进行比较，直到找到匹配项或到达数据集的末尾。在最坏的情况下，目标元素可能是数据集中的最后一个元素，这需要检查每个元素。因此，时间复杂度是线性的，运行时间随输入数据的大小线性增长。

线性查找的空间复杂度

线性查找算法的空间复杂度为 O(1)，这意味着它使用的内存量是恒定的。线性查找不需要与输入大小成比例的额外数据结构。它只使用几个变量来跟踪循环索引、目标值以及结果（找到元素的索引或未找到时为 -1）。无论数据集的大小如何，使用的空间都保持恒定。

在 C++ 中实现线性查找

让我们仔细看看如何在 C++ 中实现线性查找算法。我们将提供一个简单的代码示例来帮助您理解该过程。

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // Element found, return its index
        }
    }
    return -1; // Element not found
}

int main() {
    int data[] = {12, 45, 78, 23, 56, 89, 67, 34, 90};
    int n = sizeof(data) / sizeof(data[0]);
    int target = 67;

    int result = linearSearch(data, n, target);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found in the array." << endl;
    }

    return 0;
}

输出

Element found at index 6

解释

1. 初始化

首先，内存中有一个元素数组（或列表）。
您还有一个要在该数组中查找的目标值。

2. 迭代

从数组的第一个元素开始。
将当前元素的值与目标值进行比较。

3. 检查匹配项

如果当前元素等于目标值，则表示找到了匹配项！
在这种情况下，您将返回当前元素在数组中的索引（位置）。此索引通常是一个非负整数，表示元素在数组中的位置。

4. 无匹配项

如果当前元素不等于目标值，请移动到数组中的下一个元素。
对数组中的每个元素重复此过程（将当前元素与目标值进行比较），一次一个。

5. 数组结束

继续迭代数组，直到找到匹配项，或到达数组末尾而未找到目标值。

6. 报告结果

如果您找到目标值，则返回该元素的索引。
如果到达数组末尾而未找到目标值，则返回一个特殊值（通常为 -1）以指示未在数组中找到目标值。

关键点

线性查找是一种直接而直观的算法。
它不依赖于数组中元素的顺序；它适用于有序和无序数据。
其时间复杂度为 O(n)，其中“n”是数组中的元素数量。在最坏的情况下，您可能需要检查所有元素。
它不需要在查找之前对数据进行任何预处理，例如排序。
它适用于小型数据集，但对于非常大的数据集效率较低。

总之，线性查找算法是通过逐个检查每个元素来查找数组或列表中的特定元素的基本方法，直到找到所需元素或到达数据结构的末尾。它是理解更高级查找算法和数据结构的基本构建块。

示例 1：在数组中查找元素

在此示例中，我们有一个整数数组，并且我们希望使用线性查找在该数组中查找特定元素。

#include <iostream>
using namespace std;

int linearSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i; // Element found, return its index
        }
    }
    return -1; // Element not found
}

int main() {
    int data[] = {12, 45, 78, 23, 56, 89, 67, 34, 90};
    int n = sizeof(data) / sizeof(data[0]);
    int target = 67;

    int result = linearSearch(data, n, target);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    } else {
        cout << "Element not found in the array." << endl;
    }

    return 0;
}

输出

Element found at index 6

解释

定义一个名为 linearSearch 的函数，该函数接受三个参数
- arr[]：我们要搜索的整数数组。
- n：数组的大小。
- target：我们要查找的整数。
在 linearSearch 函数内部
- 我们使用 for 循环迭代数组中的每个元素，从第一个元素（索引 0）开始，一直到最后一个元素（索引 n - 1）。
- 对于数组中的每个元素，我们将其与目标值进行比较。
- 如果元素与目标匹配，我们返回该元素的索引，表示我们找到了该元素。
如果 for 循环在未找到目标的情况下完成（即，没有元素与目标匹配），我们返回 -1 以表示未在数组中找到该元素。
在 main 函数中，我们创建一个名为 data 的数组并用一组整数值对其进行初始化。
我们使用 sizeof 运算符计算 n 来确定 data 数组的大小。
我们指定要在数组中查找的目标值（例如，target = 67）。
我们调用 linearSearch 函数，并将 data 数组、其大小 n 和目标值作为参数传递。
搜索结果存储在 result 变量中。
然后，我们使用条件语句来检查 result 的值。如果 result 不等于 -1，我们打印一条消息，指示找到元素的索引。如果 result 为 -1，我们打印一条消息，指示未在数组中找到该元素。

示例 2：在列表中搜索姓名

在此示例中，我们有一个存储在 C++ vector 中的姓名列表，并且我们希望使用线性查找在该列表中查找特定姓名。

#include <iostream>
#include <vector>
using namespace std;

int linearSearch(vector<string> names, string target) {
    for (int i = 0; i < names.size(); i++) {
        if (names[i] == target) {
            return i; // Name found, return its index
        }
    }
    return -1; // Name not found
}

int main() {
    vector<string> nameList = {"Alice", "Bob", "Charlie", "David", "Eve", "Frank"};
    string targetName = "Eve";

    int result = linearSearch(nameList, targetName);

    if (result != -1) {
        cout << "Name found at index " << result << endl;
    } else {
        cout << "Name not found in the list." << endl;
    }

    return 0;
}

输出

Name found at index 4

解释

我们定义一个名为 linearSearch 的函数，该函数接受两个参数
- names：我们要搜索的字符串 vector。
- target：我们要查找的姓名。
在 linearSearch 函数内部
- 我们使用 for 循环迭代 vector 中的每个姓名。
- 对于 vector 中的每个姓名，我们将其与目标姓名进行比较。
- 如果姓名与目标匹配，我们返回该姓名的索引，表示我们找到了该姓名。
如果 for 循环在未找到目标的情况下完成（即，没有姓名与目标匹配），我们返回 -1 以表示未在 vector 中找到该姓名。
在 main 函数中，我们创建一个名为 nameList 的 vector 并用一组姓名对其进行初始化。
我们指定要在 vector 中查找的目标姓名（例如，targetName = "Eve"）。
我们调用 linearSearch 函数，并将 nameList vector 和 targetName 作为参数传递。
搜索结果存储在 result 变量中。
然后，我们使用条件语句来检查 result 的值。如果 result 不等于 -1，我们打印一条消息，指示找到姓名的索引。如果 result 为 -1，我们打印一条消息，指示未在 vector 中找到该姓名。

示例 3：在结构体数组中搜索学生成绩

在此示例中，我们有一个表示学生记录的结构体数组，并且我们希望使用线性查找查找特定学生的成绩。

#include <iostream>
#include <string>
using namespace std;

struct Student {
    string name;
    int grade;
};

int linearSearch(Student students[], int n, string targetName) {
    for (int i = 0; i < n; i++) {
        if (students[i].name == targetName) {
            return students[i].grade; // Student found, return the grade
        }
    }
    return -1; // Student not found
}

int main() {
    Student studentData[] = {
        {"Alice", 85},
        {"Bob", 92},
        {"Charlie", 78},
        {"David", 88},
        {"Eve", 95}
    };
    int n = sizeof(studentData) / sizeof(studentData[0]);
    string targetName = "David";

    int result = linearSearch(studentData, n, targetName);

    if (result != -1) {
        cout << "Grade for " << targetName << " is " << result << endl;
    } else {
        cout << "Student not found in the records." << endl;
    }

    return 0;
}

输出

Grade for David is 88

解释

我们首先定义一个名为 Student 的结构体。每个 Student 结构体都有两个成员：name（一个用于存储学生姓名的字符串）和 grade（一个用于存储学生成绩的整数）。
我们创建一个名为 linearSearch 的函数，该函数接受三个参数
- students[]：Student 结构体的数组。
- n：数组中的元素数量。
- targetName：我们要查找其成绩的学生姓名。
在 linearSearch 函数内部
- 我们使用 for 循环迭代 students 数组的每个元素。
- 对于每个学生，我们检查 Student 结构体的 name 成员是否与我们正在搜索的 targetName 匹配。
- 如果找到匹配项，我们返回该学生的成绩，表示我们找到了该学生的记录。
如果 for 循环在未找到具有指定姓名的学生的情况下完成，我们返回 -1 以表示未在数组中找到该学生。
在 main 函数中，我们创建一个名为 studentData 的 Student 结构体数组，并用包含姓名和成绩的学生记录对其进行初始化。
- 我们使用 sizeof 运算符计算 n 来确定 studentData 数组中的元素数量。
- 我们指定要查找其成绩的 targetName（例如，“David”）。
- 我们调用 linearSearch 函数，并将 studentData 数组、其大小 n 和 targetName 作为参数传递。
- 搜索结果存储在 result 变量中。
我们使用条件语句来检查 result 的值。如果 result 不等于 -1，我们打印一条消息，指示 targetName 姓名的学生的成绩。如果 result 为 -1，我们打印一条消息，指示未在数组中找到该学生的记录。

示例 4：检查字符串中是否存在字符

在此示例中，我们希望使用线性查找检查特定字符是否存在于字符串中。

#include <iostream>
#include <string>
using namespace std;

bool linearSearch(const string& text, char targetChar) {
    for (char c : text) {
        if (c == targetChar) {
            return true; // Character found
        }
    }
    return false; // Character not found
}

int main() {
    string text = "Hello, World!";
    char targetChar = 'W';

    bool result = linearSearch(text, targetChar);

    if (result) {
        cout << "Character '" << targetChar << "' is present in the string." << endl;
    } else {
        cout << "Character '" << targetChar << "' is not found in the string." << endl;
    }

    return 0;
}

输出

Character 'W' is present in the string.

解释

函数声明：我们创建一个名为 linearSearch 的函数，该函数接受两个参数

text：这是我们要搜索字符的字符串。

targetChar：这是我们要检查的字符，它存在于字符串中。

在字符串中搜索

在 linearSearch 函数内部，我们使用 for-each 循环迭代 text 字符串中的字符。

对于每个字符，我们将其与我们正在搜索的 targetChar 进行比较。

找到字符

如果找到匹配项，即当前字符与 targetChar 相同，我们返回 true。这表示该字符存在于字符串中。

未找到字符

如果循环在未在字符串中找到 targetChar 的情况下完成，我们返回 false。这表示该字符不存在于字符串中。

主函数

在 main 函数中，我们定义输入字符串 text（例如，“Hello, World！”）并指定要检查的 targetChar（例如，'W'）。

调用线性查找函数

我们调用 linearSearch 函数，并将 text 字符串和 targetChar 作为参数传递。

结果处理

搜索结果存储在 result 变量中。

显示结果

我们使用条件语句来检查 result 的值。如果 result 为 true，我们打印一条消息，指示该字符存在于字符串中。如果 result 为 true，我们打印一条消息，指示该字符存在于字符串中。如果 result 为 false，我们打印一条消息，指示未在字符串中找到该字符。

此代码演示了如何使用线性查找来检查给定字符串中是否存在特定字符。该算法会依次扫描字符串中的字符，如果找到字符则返回 true，如果未找到则返回 false。

应用

在无序列表中查找：当您有一个无序的项目列表，并且想查找特定项目时，线性查找是一个直接的选择。这在查找联系人列表中的姓名或查找无序数据库中的特定记录等任务中非常有用。
在简单数据库中搜索：在记录未索引或未以特定方式组织的规模较小的数据库中，可以使用线性查找来根据特定标准查找特定记录。
输入验证：可以使用线性查找来验证用户输入，方法是检查给定值是否存在于预定义列表的有效选项中或配置文件中。
查找重复项：线性查找可以识别数据集中的重复条目。这在数据清理和去重过程中很有用。
线性查找作为构建块：线性查找通常用作理解更复杂的查找算法的基础概念。它为学习二分查找、哈希表和其他高级查找技术提供了起点。
Web 浏览器和文本编辑器：线性查找在 Web 浏览器和文本编辑器中用于查找文档中的特定单词或短语。
电脑游戏：线性查找可用于查找 2D 游戏或简单游戏网格中的对象或敌人。虽然它可能不是复杂游戏环境中最高效的算法，但它适用于基本场景。
控制流逻辑：线性查找可应用于控制流逻辑。例如，您可能使用它来根据特定条件确定程序应遵循的路径。
网络路由：在某些路由算法中，可以使用线性查找来根据 IP 地址或端口号等标准查找匹配的规则来路由数据包。
资源管理：在分配或释放资源（如内存块）的情况下，线性查找可以帮助识别可用资源。

需要注意的是，虽然线性查找是一种通用的算法，但对于非常大的数据集来说，它可能不是最高效的选择。对于这种情况，更高级的算法，如二分查找、哈希表或基于树的结构，可能提供更好的性能。尽管如此，线性查找仍然是程序员工具箱中的宝贵工具，适用于特定用例，并且是理解计算机科学中查找和迭代的基本概念。

优点

易于实现：线性查找是最简单的查找算法之一，易于理解和实现。其简单的特性使其成为初学者和快速解决问题的理想选择。
适用于无序数据：线性查找在有序和无序数据上效果都一样好。它不需要任何特定的数据排列，使其适用于各种场景。
无需预处理：与许多依赖于排序数组或树等数据结构的其他查找算法不同，线性查找不需要对数据进行预处理。您可以直接将其应用于数据集，这在数据频繁更改的情况下可能更有效。
适用于小型数据集：在数据集相对较小的情况下，线性查找的速度可能与更复杂的算法一样快，甚至更快。其在最佳情况（元素位于第一个位置）下的恒定时间复杂度（O(1)）使其成为小型集合的竞争性选择。
易于调试：由于其简单性，线性查找的调试和错误跟踪更容易。这使其成为快速识别搜索过程中问题的良好选择。
诊断和验证：线性查找可以作为验证数据和执行诊断的宝贵工具。它有助于识别重复项、缺失元素和其他与数据相关的问题。
教育价值：线性查找是理解更高级查找算法和数据结构的基础概念。它为学习二分查找和基于哈希的数据结构等更复杂的算法提供了基础。
资源效率：在只需要搜索数据集一次或很少一次的情况下，实现更复杂的查找算法的开销可能不值得。线性查找是一种精简而直接的选择。
控制流逻辑：线性查找可用于在各种程序中构建控制流逻辑，帮助您根据数据集中某些元素的出现或不存在来做出决策。
动态数据：对于大小经常变化的数据结构，如动态数组或列表，可以使用线性查找来有效定位元素，而无需重新组织数据结构。

缺点

对于大型数据集效率低下：线性查找的时间复杂度为 O(n)，其中“n”表示数据集中的元素数量。这意味着查找元素所需的时间随数据集大小线性增长。对于非常大的数据集，该算法可能很慢且不切实际。
最坏情况：在最坏的情况下，当目标元素位于数据集的末尾或根本不存在时，线性查找需要检查每个元素。这会导致最长的执行时间。
不从数据排序中获益：线性查找不利用排序数据。无论数据是否排序，它都需要逐个检查每个元素，这使得它对于有序数据集效率较低，而对于有序数据集，像二分查找这样的其他算法性能会显著提高。
不适用于重复搜索：如果您需要搜索同一数据集中的多个元素，线性查找可能会变得效率低下。哈希表或二叉搜索树等其他数据结构更适合重复搜索。
不适用于实时系统：在需要实时响应或极低延迟的应用中，线性查找可能无法满足速度要求。在这些情况下，需要更快的查找算法。
可扩展性有限：随着数据集大小的增长，线性查找所需的时间也会增加。这限制了算法的可扩展性及其对大规模应用程序的适用性。
资源效率低下：对于大型数据集，线性查找可能不是计算能力和内存使用方面最高效的算法。更高效的算法可以更有效地利用资源。
不从部分匹配中获益：线性查找无法利用部分匹配或模糊搜索技术。它只能确定是否存在精确匹配，如果不存在，它需要遍历整个数据集。
错失优化机会：线性查找无法从优化特定类型搜索的高级数据结构中获益。例如，它不使用树结构来进行更有效的搜索操作。
依赖于数据排列：虽然它不需要数据排序，但线性查找的效率取决于数据的排列。在某些情况下，数据的组织方式可能使线性查找效率低下。

结论

线性查找，也称为顺序查找，是一种简单且基础的计算机科学查找算法。它是一种在数据集中（无论是数组、列表还是任何线性结构）查找特定元素或数据的简单方法。线性查找按顺序迭代元素，将每个元素与目标值进行比较，直到找到匹配项或搜索完整个数据集。它的特点是简单、易于实现以及 O(n) 的时间复杂度。

线性查找在现实世界的各种场景中有多种应用，从在列表中搜索项目到在无序数据集中查找特定数据。它可用于各种编程语言，包括 C++，如提供的示例所示。尽管它不是查找大型数据集最高效的算法，但它仍然是计算机科学初学者的一项基本概念，有助于他们建立对算法和问题解决技术的根本理解。

总之，线性查找可能不是查找大型或排序数据集最快的查找方法，但它是程序员工具箱中的一个有价值的工具，在数据未为更复杂的查找技术进行组织的情况下，它提供了简单性和可靠性。理解线性查找是程序员掌握算法和数据结构的必经之路。

下一主题C++ 中最快的排序算法

C++ 线性搜索算法

引言

什么是线性查找？

演变

线性查找的关键特性

时间和空间复杂度

在 C++ 中实现线性查找

示例 1：在数组中查找元素

示例 2：在列表中搜索姓名

示例 3：在结构体数组中搜索学生成绩

示例 4：检查字符串中是否存在字符

应用

优点

缺点

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 线性搜索算法

引言

什么是线性查找？

演变

线性查找的关键特性

时间和空间复杂度

在 C++ 中实现线性查找

示例 1：在数组中查找元素

示例 2：在列表中搜索姓名

示例 3：在结构体数组中搜索学生成绩

示例 4：检查字符串中是否存在字符

应用

优点

缺点

结论

相关帖子

C++ 酒店管理

C++ 程序生成长度为 n 的 Lyndon Words

C++ STL 中的数组求和

C++ 大学管理系统

C++ 中 deque::assign 和 deque::empty 的区别

在 C++ 的 Map 中按值搜索