线性搜索

提示

1. 基本概念：线性搜索是一种简单的搜索算法，按顺序检查每个列表元素，直到找到目标元素。
2. 搜索过程：从列表的第一个元素开始，逐个与目标值比较，如果找到匹配，则返回其索引；如果遍历整个列表都未找到，则返回“未找到”。
3. 效率和应用：时间复杂度为 O(n)，空间复杂度为 O(1)，适用于小型数组（小于100个元素）的搜索。

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

线性搜索的工作原理

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

1. 从第一个元素开始，将 k 与每个元素 x 进行比较。

   

2. 如果 x == k，返回索引。

3. 否则，返回 未找到。

线性搜索算法

LinearSearch(array, key)
  对于数组中的每个项
    如果项等于值
      返回其索引

Python、Java 和 C/C++ 示例

Python Java C C++

# Python中的线性搜索

def linearSearch(array, n, x):

    # 顺序遍历数组
    for i in range(0, n):
        if (array[i] == x):
            return i
    return -1


array = [2, 4, 0, 1, 9]
x = 1
n = len(array)
result = linearSearch(array, n, x)
if(result == -1):
    print("未找到元素")
else:
    print("元素位于索引: ", result)

// Java中的线性搜索

class LinearSearch {
  public static int linearSearch(int array[], int x) {
  int n = array.length;

  // 顺序遍历数组
  for (int i = 0; i < n; i++) {
    if (array[i] == x)
    return i;
  }
  return -1;
  }

  public static void main(String args[]) {
  int array[] = { 2, 4, 0, 1, 9 };
  int x = 1;

  int result = linearSearch(array, x);

  if (result == -1)
    System.out.print("未找到元素");
  else
    System.out.print("元素位于索引: " + result);
  }
}

// C中的线性搜索

#include <stdio.h>

int search(int array[], int n, int x) {

  // 顺序遍历数组
  for (int i = 0; i < n; i++)
    if (array[i] == x)
      return i;
  return -1;
}

int main() {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

  int result = search(array, n, x);

  (result == -1) ? printf("未找到元素") : printf("元素位于索引: %d", result);
}

// C++中的线性搜索

#include <iostream>
using namespace std;

int search(int array[], int n, int x) {

  // 顺序遍历数组
  for (int i = 0; i < n; i++)
    if (array[i] == x)
      return i;
  return -1;
}

int main() {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

  int result = search(array, n, x);

  (result == -1) ? cout << "未找到元素" : cout << "元素位于索引: " << result;
}

线性搜索复杂性

时间复杂性： O(n)

空间复杂性： O(1)

线性搜索应用

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