设计与分析 - 线性搜索

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

例如，在给定的动画图中，我们正在搜索元素 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

^{将数组的第 4个}索引 47中的元素与键 47 进行比较。发现两个元素都匹配。现在，返回47所在的位置，即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) { // compares each element of the array
         printf("The element is found at %d position\n", i+1);
         count = count + 1;
      }
   }
   if(count == 0) // for unsuccessful search
      printf("The element is not present in the array\n");
}
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) { // compares each element of the array
       cout << "The element is found at position " << i+1 <<endl;
       count = count + 1;
     }
   }
   if(count == 0) // for unsuccessful search
     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) { // compares each element of the array
            System.out.println("The element is found at position " + (i+1));
            count = count + 1;
         }
      }
      if(count == 0) // for unsuccessful search
         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("Unsuccessful Search")

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
Unsuccessful Search