线性搜索是一种顺序搜索算法，我们从一端开始检查列表中的每个元素，直到找到所需的元素。它是最简单的搜索算法。

线性搜索的图解

按照以下步骤k = 1在下面的列表中搜索元素。

线性搜索（Linear Search） - 图1
要搜索的数组
  1. 从第一个元素开始，比较 克 与每个元素 X. | 线性搜索（Linear Search） - 图2 | | —- | | 与每个元素进行比较 |
  1. 如果x == k，则返回索引。 | 线性搜索（Linear Search） - 图3 | | —- | | 找到元素 |
  1. 否则，返回未找到.

线性搜索的伪码

  1. LinearSearch(array, key)
  2.   for each item in the array
  3.     if item == value
  4.       return its index

线性搜索的实现

  1. // Linear Search in Java
  3. class LinearSearch {
  4.   public static int linearSearch(int array[], int x) {
  5.   int n = array.length;
  7.   // Going through array sequencially
  8.   for (int i = 0; i < n; i++) {
  9.     if (array[i] == x)
  10.     return i;
  11.   }
  12.   return -1;
  13.   }
  15.   public static void main(String args[]) {
  16.   int array[] = { 2, 4, 0, 1, 9 };
  17.   int x = 1;
  19.   int result = linearSearch(array, x);
  21.   if (result == -1)
  22.     System.out.print("Element not found");
  23.   else
  24.     System.out.print("Element found at index: " + result);
  25.   }
  26. }

线性搜索复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

线性搜索的应用

  1. 用于在较小数组（<100 项）中进行搜索操作。