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。

例子：

// C++ 程序进行线性搜索
// 在 arr[] 中查找 x。
// 如果 x 存在，则返回其位置，
// 否则返回 -1。
#include <iostream>
using namespace std;
 
int search(int arr[],
           int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
 
// 驱动程序
int main(void)
{
    int arr[] = {2, 3, 4, 10, 40};
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
   
    // 调用函数
    int result = search(arr, n, x);
    (result == -1) ?
     cout << "元素不存在于数组中" :
     cout << "元素存在于索引 " <<
              result;
    return 0;
}  

输出

元素存在于索引 3

上述算法的 时间复杂度 为 O(n)。

上述算法的 空间复杂度 为 O(1)，因为没有使用额外的空间。

线性搜索在实际中很少使用，因为其他搜索算法，如二进制搜索算法和哈希表，允许与线性搜索相比更快的搜索速度。

改善线性搜索的最坏时间复杂度

1. 如果元素在最后找到，则 O(n) 到 O(1)
2. 这与之前的方法相同，因为在此处我们在一次循环的迭代中执行了 2 个“if”操作，而在先前的方法中，我们仅执行了 1 个“if”操作。这使两个时间复杂度相同。

下面是实现代码：

// C++程序用于线性搜索
#include<bits/stdc++.h>
using namespace std;
 
void search(vector<int> arr,
            int search_Element)
{
    int left = 0;
    int length = arr.size();
    int position = -1;
      int right = length - 1;
       
    // 从0到right循环
    for(left = 0; left <= right;)
    {
         
        // 如果左边找到了search_element
        if (arr[left] == search_Element)
        {
             
            position = left;
            cout << "在数组中找到元素位置为 " <<
                     position + 1 << " 尝试 " <<
                     left + 1;
                
            break;
        }
       
        // 如果右边找到了search_element
        if (arr[right] == search_Element)
        {
            position = right;
            cout << "在数组中找到元素位置为 " <<
                     position + 1 << " 尝试 " <<
                     length - right;
                
            break;
        }
        left++;
        right--;
    }
 
    // 如果没有找到元素
    if (position == -1)
        cout << "在数组中未找到元素，尝试次数为 "
             << left;
}
 
// 主程序
int main()
{
    vector<int> arr{1, 2, 3, 4, 5};
    int search_element = 5;
     
    // 调用函数
    search(arr, search_element);
}
     
// 鸣谢：mayanktyagi1709```  

输出

在数组中找到元素位置为 5 尝试 1

时间复杂度： O(n)

辅助空间： O(1)