C 语言哨兵线性搜索程序

哨兵线性搜索是线性搜索算法的改进版本。与线性搜索相比，它的比较次数更少。

线性搜索

它也被称为顺序搜索。它是用于在给定数组或元素列表中查找目标元素的最基本算法。线性搜索的时间复杂度为 O(n)。最佳情况时间复杂度为 O(1)，最坏情况时间复杂度为 O(n)，其中 n 是列表或数组中的元素数量。

哨兵线性搜索

它是线性搜索的一种变体。它引入了一个哨兵值，一个放置在数组末尾的特殊值。它作为停止条件，消除了在循环中检查数组末尾的需要。这种优化将比线性搜索具有更好的时间复杂度。

示例

让我们看一个 C 程序来演示哨兵线性搜索：

输出

说明

在此程序中，哨兵值暂时添加到数组的末尾，从而无需在循环中进行额外检查即可进行更高效的搜索。该算法遍历数组，直到找到目标值，一旦搜索完成，哨兵将替换为原始的最后一个元素。之后，主函数初始化一个数组并演示了如何使用哨兵线性搜索来查找目标元素的索引，清晰地指示元素是否存在于数组中以及在哪个索引处。

示例 2

让我们看一个 C 程序来查找哨兵线性搜索和传统线性搜索所需的时间。

输出

说明

• linearSearch 函数

linearSearch函数实现传统的线性搜索算法，遍历数组以查找目标值。如果找到目标，它返回目标的索引，否则返回 -1。

• sentinelLinearSearch 函数

sentinelLinearSearch函数通过在数组末尾添加一个哨兵值来优化线性搜索。之后，它遍历数组，在找到目标值时有效地终止搜索。如果找到目标，它返回目标的索引，否则返回 -1。

• measureExecutionTime 函数

measureExecutionTime函数计算给定搜索算法的执行时间。使用clock()函数，它测量执行搜索之前和之后的时间，以秒为单位提供执行时间。该函数有助于比较不同搜索算法的性能。

• 主函数

main函数初始化一个数组，并使用measureExecutionTime函数测量线性搜索和哨兵线性搜索的执行时间。它打印执行时间以及通过使用哨兵线性搜索算法节省的时间，从而深入了解优化的效率。