C++ 哨兵线性搜索程序

2024 年 8 月 29 日 | 阅读 12 分钟

在本文中，我们将讨论使用不同方法的 C++ 哨兵线性搜索程序。但在讨论其实现之前，我们必须了解 C++ 中的哨兵线性搜索。

什么是哨兵线性搜索？

“哨兵线性搜索” 是线性搜索算法的一种变体，它使用哨兵值来简化代码。哨兵是放置在数组末尾的特殊值，它被选择为保证不是有效输入。在搜索上下文中，哨兵值被设置为等于搜索键。

方法 1：将哨兵线性搜索实现为函数

实现为函数的哨兵线性搜索涉及将搜索逻辑封装在独立的函数中。此函数将要搜索的数组、其大小和要查找的键作为参数。以下是详细说明：

示例

#include <iostream>
// Sentinel Linear Search function
int sentinelLinearSearch(int arr[], int size, int key) {
 // Set sentinel value at the end of the array
 arr[size - 1] = key;
 // Initialize index to 0
 int index = 0;
 // Search loop
 while (arr[index] != key) {
 index++;
 }
 // Result handling
 if (index < size - 1) {
 return index; // Key found
 } else {
 return -1; // Key not found
 }
}
int main() {
 const int size = 5;
 int arr[size] = {10, 20, 30, 40, 50};
 int key = 30;
 // Call the Sentinel Linear Search function
 int result = sentinelLinearSearch(arr, size, key);
 // Display the result
 if (result != -1) {
 std::cout << "Element found at index " << result << std::endl;
 } else {
 std::cout << "Element not found in the array." << std::endl;
 }
 return 0;
}

输出

Element found at index 2

说明

参数

arr： 要搜索的数组。
size： 数组的大小。
key： 要查找的键。

哨兵初始化

该函数将数组的最后一个元素设置为搜索键。它有效地创建了一个哨兵值。

搜索循环

该函数使用 while 循环遍历数组，直到找到哨兵值（键）。
循环递增索引变量，直到 arr[index] 等于哨兵值。

结果处理

如果索引小于 size - 1，则找到键，函数返回 索引。
如果索引等于 size - 1，则未找到键，并 返回 -1。

主函数

数组初始化

创建了一个示例数组 arr，其值为 {10, 20, 30, 40, 50}。
要搜索的键设置为 30。

函数调用

使用数组、其大小和键调用 sentinelLinearSearch 函数。
结果存储在 result 变量中。

结果显示

根据结果，程序会打印元素是否找到。
如果结果不为 -1，则打印找到键的 索引； 否则，它表示元素不在数组中。

复杂度分析

时间复杂度

哨兵线性搜索的时间复杂度由搜索循环中的迭代次数决定。在最坏的情况下，循环会一直遍历整个数组，直到找到哨兵值（搜索键）或到达末尾。因此，时间复杂度为 O(n)， 其中 n 是数组的大小。

空间复杂度

空间复杂度是指算法使用的额外内存量。在提供的代码中：

输入（数组）的空间复杂度：O(n)， 其中 n 是数组的大小。数组是算法的主要输入，其空间复杂度直接与其大小成正比。

变量的空间复杂度：O(1)。 像 index、key 和 result 这样的变量所需的空间是恒定的，不取决于输入数组的大小。

整个算法的空间复杂度由算法需要分配的最大内存量决定。在这种情况下，它被输入数组的大小所主导。

方法 2：使用类

利用类来实现哨兵线性搜索，可以有机会将搜索逻辑封装在内聚和 面向对象 的结构中。在此范例中，搜索过程的细节被封装在类的构造中，从而促进了模块化和可维护性。以下示例阐释了哨兵线性搜索在类中的集成，展示了更 结构化 的面向对象的方法。

示例

#include <iostream>
class SentinelLinearSearch {
public:
 SentinelLinearSearch(int arr[], int size, int key) {
 // Set sentinel value at the end of the array
 arr[size - 1] = key;
 // Search loop
 for (index = 0; arr[index] != key; ++index) {
 // No need for an explicit loop condition
 // The loop will terminate when arr[index] == key
 }
 // Result handling
 result = (index < size - 1) ? index : -1; // Ternary operator for result
 // Display the result
 if (result != -1) {
 std::cout << "Element found at index " << result << std::endl;
 } else {
 std::cout << "Element not found in the array." << std::endl;
 }
 }
private:
 int index; // Index where the key is found
 int result; // Final result
};
int main() {
 const int size = 5;
 int arr[size] = {10, 20, 30, 40, 50};
 int key = 40;
 // Instantiate the SentinelLinearSearch class
 SentinelLinearSearch searcher(arr, size, key);
 return 0;
}

输出

Element found at index 3

说明

构造函数

该类有一个 构造函数，在实例化时调用。它将数组（arr）、其大小（size）和要查找的键（key）作为参数。

哨兵初始化

构造函数将数组的最后一个元素设置为搜索键。这建立了一个哨兵值。

搜索循环

使用 for 循环遍历数组，直到找到 哨兵值（键）。

循环递增索引变量，直到 arr[index] 等于哨兵值。

结果处理

找到键的索引存储在 result 变量中。
使用三元运算符确定结果，并显示该值。

main 函数

数组初始化

创建了一个示例数组 arr，其值为 {10, 20, 30, 40, 50}。

要搜索的键设置为 30。

类实例化

通过将数组、其大小和键传递给构造函数来创建 SentinelLinearSearch 类 的实例。

复杂度分析

时间复杂度

哨兵线性搜索的时间复杂度由搜索循环中的迭代次数决定。在最坏的情况下，循环会一直遍历整个数组，直到找到哨兵值（搜索键）或到达末尾。因此，时间复杂度为 O(n)， 其中 n 是数组的大小。

空间复杂度

空间复杂度是指算法使用的额外内存量。

输入（数组）的空间复杂度：O(n)，其中 n 是数组的大小。数组是算法的主要输入，其空间复杂度直接与其大小成正比。

类中变量的空间复杂度

index：O(1) - 用于在搜索过程中跟踪索引的单个变量。

result：O(1) - 用于存储最终结果的单个变量。

key（在构造函数中）：O(1) - 存储键的单个变量。

main 中局部变量的空间复杂度

size：O(1) - 存储数组大小的恒定大小变量。

arr：O(n) - 输入数组。

key：O(1) - 要搜索的键。

算法的总体空间复杂度受输入数组大小的支配，导致 O(n) 空间复杂度。

方法 3：使用 do-while 循环

在此方法中，我们使用 do-while 循环来确保 循环体 至少执行一次。如果您想确保即使在数组为空时也执行搜索逻辑，此方法很有用。

示例

#include <iostream>
int sentinelLinearSearch(int arr[], int size, int key) {
 // Set sentinel value at the end of the array
 arr[size - 1] = key;
 // Initialize index to 0
 int index = 0;
 // Search loop using do-while
 do {
 if (arr[index] == key) {
 return index; // Key found
 }
 index++;
 } while (true);
 // The loop should never reach this point
 return -1; // To satisfy the compiler, but it's unreachable
}
int main() {
 const int size = 5;
 int arr[size] = {10, 20, 30, 40, 50};
 int key = 30;
 // Call the Sentinel Linear Search function
 int result = sentinelLinearSearch(arr, size, key);
 // Display the result
 if (result != -1) {
 std::cout << "Element found at index " << result << std::endl;
 } else {
 std::cout << "Element not found in the array." << std::endl;
 }
 return 0;
}

输出

Element found at index 0

说明

哨兵线性搜索函数

函数 sentinelLinearSearch 接受 三个参数： arr（要搜索的数组）、size（数组的大小）和 key（要找到的元素）。
在数组末尾设置一个哨兵值（arr[size - 1] = key），确保搜索的终止条件。
该函数将索引变量初始化为 0。
之后，它进入一个 do-while 循环，该循环始终至少执行一次。在循环内，它检查当前索引处的元素 (arr[index]) 是否等于搜索键。如果为真，则返回索引，表示找到键。
循环递增索引，直到遇到哨兵值。

主函数

main 函数使用值 {10, 20, 30, 40, 50} 初始化数组 arr，并将要搜索的键设置为（key = 30）。
然后调用 sentinelLinearSearch 函数，传递数组、其大小和键。
结果存储在 result 变量中。
最后，根据结果显示元素是否找到。

复杂度分析

时间复杂度

哨兵线性搜索的时间复杂度由搜索循环中的迭代次数决定。在此实现中：

循环线性遍历数组，直到找到哨兵值（搜索键）或到达末尾。
在最坏的情况下，循环可能需要遍历整个数组。
因此，时间复杂度为 O(n)， 其中 n 是数组的大小。

空间复杂度

空间复杂度是指算法使用的额外内存量。

输入（数组）的空间复杂度：O(n)， 其中 n 是数组的大小。数组是算法的主要输入，其空间复杂度直接与其大小成正比。

变量的空间复杂度

index：O(1) - 用于在搜索过程中跟踪索引的单个变量。

key（参数）：O(1) - 存储键的单个变量。

循环条件的空间复杂度

do-while 循环条件除了循环控制变量（索引）之外，不需要额外的空间。
由于输入数组的大小，算法的总体空间复杂度为 O(n)， 该大小主导了空间需求。

方法 4：递归实现

另一种方法是使用递归进行搜索。由于大型数组可能 导致堆栈溢出，这可能不是最高效的方法，但它展示了一种不同的表达算法的方式。

示例

#include <iostream>
int sentinelLinearSearchRecursive(int arr[], int index, int size, int key) {
 // Set sentinel value at the end of the array
 arr[size - 1] = key;
 // Base case: if key is found
 if (arr[index] == key) {
 return index;
 }
 // Recursive case: continue searching
 return sentinelLinearSearchRecursive(arr, index + 1, size, key);
}
int main() {
 const int size = 5;
 int arr[size] = {10, 20, 30, 40, 50};
 int key = 50;
 // Call the Sentinel Linear Search function recursively
 int result = sentinelLinearSearchRecursive(arr, 0, size, key);
 // Display the result
 if (result != -1) {
 std::cout << "Element found at index " << result << std::endl;
 } else {
 std::cout << "Element not found in the array." << std::endl;
 }
 return 0;
}

输出

Element found at index 4

说明

SentinelLinearSearchRecursive 函数

参数

arr： 要搜索的数组。

index： 当前正在检查的索引。

size： 数组的大小。

key： 要在数组中查找的键。

该函数在数组末尾设置哨兵值 (arr[size - 1] = key)，以简化递归调用的终止条件。
基本情况：如果当前索引处的元素等于搜索键 (arr[index] == key)，则函数返回索引，表示找到键。
递归情况：如果不满足基本情况，则函数使用 递增的索引 递归调用自身，继续搜索。
递归调用有效地遍历数组，直到找到键或到达数组末尾。

main 函数

初始化一个数组 arr，其值为 {10, 20, 30, 40, 50}，并将要搜索的键设置为（key = 30）。
使用数组、起始索引（0）、数组大小和键调用 sentinelLinearSearchRecursive 函数。
将结果存储在 result 变量中。
根据结果显示元素是否找到。

复杂度分析

时间复杂度

递归哨兵线性搜索的时间复杂度由直到达到基本情况的递归调用次数决定。在此实现中：

该函数进行递归调用，直到找到键或到达数组末尾。

在最坏的情况下，算法可能需要遍历整个数组。

因此，时间复杂度为 O(n)， 其中 n 是数组的大小。

空间复杂度

空间复杂度是指算法使用的额外内存量。

递归栈：O(n) - 空间复杂度由递归栈的最大深度决定。在最坏的情况下，递归栈的深度等于数组的大小，因为每次递归调用都会向栈添加一个新帧。

其他变量：O(1) - 附加变量（index、size、key）使用恒定空间。这些变量不会随着输入大小的增加而增加。

总体空间复杂度受递归栈的支配，导致 O(n) 空间复杂度。

应用

哨兵线性搜索算法在其应用的各个领域中，目标是在数据集合中定位特定元素。它的简单性和效率使其适用于某些场景。让我们详细探讨哨兵线性搜索的几个应用：

数据库管理系统

在 数据库管理系统 中，哨兵线性搜索可用于在数据库中搜索记录。考虑一个场景，其中数据库包含用户信息，我们需要确定某个用户是否存在于系统中。通过使用哨兵线性搜索，算法会遍历 用户记录，直到找到匹配项或到达数据库末尾。当数据库未排序且需要顺序搜索时，此方法特别适用。

文本处理和解析

在文本处理应用程序中，可以使用哨兵线性搜索来查找特定 模式或关键字 在文本文档中。例如，在文字处理程序中，该算法可能用于在文档中识别特定单词或短语的出现。哨兵值确保搜索一直进行到文本末尾，从而可以对内容进行全面检查。

信息检索系统

在 信息检索系统 中，其中对大型数据集进行索引和搜索以获取相关信息，哨兵线性搜索可以发挥作用。例如，在文档检索系统中，该算法可用于确定特定关键字或 文档 ID 是否存在于索引集合中。哨兵线性搜索的简单性使其适用于数据未排序或索引的数据集。

数据传输中的错误检测

在网络和通信系统中，哨兵线性搜索可用于错误检测。通过在传输的数据序列末尾附加哨兵值，接收器可以使用搜索算法来确保数据已正确接收。如果未找到哨兵值，则表示 潜在错误 或 传输不完整，从而触发适当的错误处理机制。

结论

哨兵线性搜索算法虽然对于大型数据集不是最高效的，但在简单性、易于实现和顺序搜索可接受的情况下具有实际应用。它的 多功能性 使其适用于一系列应用，从数据库管理到文本处理、网络、教育系统和游戏开发。了解哨兵线性搜索的优点和局限性，使开发人员能够为特定用例选择最合适的算法，优化性能 并 实现期望的结果。

下一主题C++ 执行任意矩阵 LU 分解的程序

C++ 哨兵线性搜索程序

什么是哨兵线性搜索？

方法 1：将哨兵线性搜索实现为函数

方法 2：使用类

方法 3：使用 do-while 循环

方法 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++ 哨兵线性搜索程序

什么是哨兵线性搜索？

方法 1：将哨兵线性搜索实现为函数

方法 2：使用类

方法 3：使用 do-while 循环

方法 4：递归实现

应用

结论

相关帖子

C++ 神经网络

C++ 中输入给定字符串所需的最小按键次数

C++ GUI

C++ 线程安全队列

C++ 用户定义大小的二维向量

C++ OFFSETOF() 宏

std::swap 和 std::vector::swap 的区别

使用 Kruskal 算法的最小生成树（C++）

C++ 抽象工厂设计模式

C++ 按频率排序元素

订阅 Tpoint Tech

联系信息

关注我们