线性搜索

  • Z时代
  • 2024-01-10
  • 分类：综合

线性搜索技术是最简单的技术。在这种技术中，项目被一个一个地搜索。此过程也适用于未排序的数据集。线性搜索也称为顺序搜索。它被命名为线性，因为它的时间复杂度是 n 的数量级O(n)。

线性搜索技术的复杂性

  • 时间复杂度： O(n)

  • 空间复杂度： O(1)

输入和输出

Input:
A list of data:
20 4 89 75 10 23 45 69
the search key 10
Output:
在以下位置找到的物品： 4

算法

linearSearch(array, size, key)

输入 -一个排序的数组，数组的大小和搜索键

输出 - 密钥的位置（如果找到），否则位置错误。

Begin
   for i := 0 to size -1 do
      if array[i] = key then
         return i
   done
   return invalid location
End

示例

#include<iostream>
using namespace std;
int linSearch(int array[], int size, int key) {
   for(int i = 0; i<size; i++) {
      if(array[i] == key) //在数组的每个位置搜索关键字
         return i; //第一次找到钥匙的位置
   }
   return -1; //当密钥不在列表中时
}
int main() {
   int n, searchKey, loc;
   cout << "输入项目数： ";
   cin >> n;
   int arr[n]; //创建一个大小为 n 的数组
   cout << "输入项目： " << endl;
   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }
   cout << "输入搜索键在列表中搜索： ";
   cin >> searchKey;
   if((loc = linSearch(arr, n, searchKey)) >= 0)
      cout << "在以下位置找到的物品： " << loc << endl;
   else
      cout << "在列表中找不到项目。" << endl;
}
输出结果
输入项目数： 8
输入项目：
20 4 89 75 10 23 45 69
输入搜索键在列表中搜索： 10
在以下位置找到的物品： 4

以上是 线性搜索 的全部内容， 来源链接： utcz.com/z/341480.html

回到顶部