线性搜索算法

线性搜索是一种顺序搜索算法。在这种方法中，遍历输入数组中的每个元素，并将其与要查找的关键元素进行比较。如果在数组中找到匹配项，则搜索成功；如果没有找到匹配项，则搜索失败，并给出最坏情况的时间复杂度。

例如，在给定的动画图中，我们正在搜索元素 33。因此，线性搜索方法会从第一个元素开始顺序搜索，直到找到匹配项。这将返回搜索成功。

在同一个图中，如果我们要搜索元素 46，则返回搜索失败，因为输入中不存在 46。

线性搜索算法

线性搜索算法相对简单。该过程从输入数组的第一个索引开始搜索。

步骤 1 − 从输入数组的第 0 个索引开始，将键值与第 0 个索引中的值进行比较。

步骤 2 − 如果值与键匹配，则返回找到该值的位置。

步骤 3 − 如果值与键不匹配，则比较数组中的下一个元素。

步骤 4 − 重复步骤 3，直到找到匹配项。返回找到匹配项的位置。

步骤 5 − 如果搜索不成功，则打印该元素不在数组中并退出程序。

伪代码

procedure linear_search (list, value)
   for each item in the list
      if match item == value
         return the item's location
      end if
   end for
end procedure

分析

线性搜索按顺序遍历每个元素，因此，最佳情况是第一次迭代就找到该元素。最佳时间复杂度为O(1)。

然而，线性搜索方法的最坏情况是搜索失败，即在数组中找不到键值，它会执行 n 次迭代。因此，线性搜索算法的最坏时间复杂度为 O(n)。

示例

让我们看一下使用线性搜索方法逐步搜索数组中的关键元素（例如 47）。

步骤 1

线性搜索从索引 0 开始。将键元素与第 0 个索引值 34 进行比较。

然而，47 ≠ 34。因此，它移动到下一个元素。

步骤 2

现在，将键与数组第一个索引值进行比较。

仍然，47 ≠ 10，因此算法继续进行另一次迭代。

步骤 3

将下一个元素 66 与 47 进行比较。它们都不匹配因此算法会比较后续元素。

步骤 4

现在，将第三个索引中的元素 27 与键值 47 进行比较。它们不相等，因此算法继续检查下一个元素。

步骤 5

将数组中第四个索引中的元素 47 与键 47 进行比较。结果发现两个元素都匹配。现在，返回 47 所在的位置，即 4。

输出结果为"在第 4 个索引处找到元素"。

实现

在本教程中，可以看到线性搜索程序以四种编程语言实现。该函数将输入元素与键值进行比较，并返回键在数组中的位置；如果键不在数组中，则返回搜索失败的提示。

#include <stdio.h>
void linear_search(int a[], int n, int key){
   int i, count = 0;
   for(i = 0; i < n; i++) {
      if(a[i] == key) { // 比较数组的每个元素
         printf("The element is found at %d position
", i+1);
         count = count + 1;
      }
   }
   if(count == 0) // 搜索失败
      printf("The element is not present in the array
");
}
int main(){
   int i, n, key;
   n = 6;
   int a[10] = {12, 44, 32, 18, 4, 10};
   key = 18;
   linear_search(a, n, key);
   key = 23;
   linear_search(a, n, key);
   return 0;
}

The element is found at 4 position
The element is not present in the array

#include <iostream>
using namespace std;
void linear_search(int a[], int n, int key){
   int i, count = 0;
   for(i = 0; i < n; i++) {
     if(a[i] == key) { // 比较数组的每个元素
       cout << "The element is found at position " << i+1 <<endl;
       count = count + 1;
     }
   }
   if(count == 0) // 搜索失败
     cout << "The element is not present in the array" <<endl;
}
int main(){
   int i, n, key;
   n = 6;
   int a[10] = {12, 44, 32, 18, 4, 10};
   key = 18;
   linear_search(a, n, key);
   key = 23;
   linear_search(a, n, key);
   return 0;
}

The element is found at position 4
The element is not present in the array

import java.io.*;
import java.util.*;
public class LinearSearch {
   static void linear_search(int a[], int n, int key) {
      int i, count = 0;
      for(i = 0; i < n; i++) {
         if(a[i] == key) { // 比较数组的每个元素
            System.out.println("The element is found at position " + (i+1));
            count = count + 1;
         }
      }
      if(count == 0) // 搜索失败
         System.out.println("The element is not present in the array");
      }
   public static void main(String args[]) {
      int i, n, key;
      n = 6;
      int a[] = {12, 44, 32, 18, 4, 10, 66};
      key = 10;
      linear_search(a, n, key);
      key = 54;
      linear_search(a, n, key);
   }
}

The element is found at position 6
The element is not present in the array

def linear_search(a, n, key):
   count = 0
   for i in range(n):
      if(a[i] == key):
         print("The element is found at position", (i+1))
         count = count + 1
   if(count == 0):
      print("The element is not present in the array")

a = [14, 56, 77, 32, 84, 9, 10]
n = len(a)
key = 32
linear_search(a, n, key)
key = 3
linear_search(a, n, key)

The element is found at position 4
The element is not present in the array