C++ 程序 线性搜索
问题: 给定一个由 n 个元素组成的数组 arr[],编写一个函数在 arr[] 中搜索给定的元素 x。
例子:
输入: arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 110;
输出: 6
元素 x 存在于索引 6 处
输入: arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 175;
输出: -1
元素 x 不存在于 arr[] 中。
一个简单的方法是 线性搜索 ,即
- 从 arr[] 的最左边的元素开始,逐个与 arr[] 中的每个元素进行比较
- 如果 x 与某个元素匹配,则返回该索引。
- 如果 x 与任何元素都不匹配,则返回 -1。
例子:
输出
上述算法的 时间复杂度 为 O(n)。
上述算法的 空间复杂度 为 O(1),因为没有使用额外的空间。
线性搜索在实际中很少使用,因为其他搜索算法,如二进制搜索算法和哈希表,允许与线性搜索相比更快的搜索速度。
改善线性搜索的最坏时间复杂度
- 如果元素在最后找到,则 O(n) 到 O(1)
- 这与之前的方法相同,因为在此处我们在一次循环的迭代中执行了 2 个“if”操作,而在先前的方法中,我们仅执行了 1 个“if”操作。这使两个时间复杂度相同。
下面是实现代码:
输出
时间复杂度: O(n)
辅助空间: O(1)