博客

详解顺序查找算法原理与使用方法

顺序查找算法

算法概述

顺序查找（Sequential Search）算法，又称线性查找，是一种最简单直观的查找算法。顺序查找是从数组的一端依次查找，直到找到目标元素或者全部查找完毕。因此，该算法的时间复杂度为 O(n)。

算法流程

  1. 从数组的第一个元素开始遍历，逐个比较元素。
  2. 如果找到目标元素，则返回它在数组中的下标。
  3. 如果遍历完整个数组仍未找到目标元素，则返回 -1。

代码示例

Python

def sequential_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

arr = [1, 5, 9, 18, 25, 6, 12]
target = 25
print(sequential_search(arr, target)) # 输出4，因为25在数组中的下标为4

JavaScript

function sequentialSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

const arr = [1, 5, 9, 18, 25, 6, 12];
const target = 25;
console.log(sequentialSearch(arr, target)); // 输出4，因为25在数组中的下标为4

使用场景

顺序查找算法适用于以下情况：

  • 数组长度较小，且没有特殊的排列方式。
  • 只需要查找一次。
  • 对数据的存储空间要求较小。

示例说明

假设有一个存储学生信息的数组students，其中每个元素代表一个学生的信息（如姓名、年龄、成绩等）。现在需要查询是否有年龄为20岁的学生。

students = [
    {'name': 'Tom', 'age': 18, 'score': 85},
    {'name': 'Jerry', 'age': 19, 'score': 92},
    {'name': 'Lucy', 'age': 20, 'score': 88},
    {'name': 'Mike', 'age': 21, 'score': 90},
    {'name': 'Mary', 'age': 19, 'score': 78}
]

target_age = 20
index = sequential_search([student['age'] for student in students], target_age)

if index != -1:
    target_student = students[index]
    print('找到了年龄为{}岁的学生，其姓名为{}，成绩为{}'.format(target_age, target_student['name'], target_student['score']))
else:
    print('未找到年龄为{}岁的学生'.format(target_age))

其中使用列表推导式将students数组中的年龄抽取出来形成新的数组作为顺序查找的输入，最终output为：

找到了年龄为20岁的学生，其姓名为Lucy，成绩为88

再以另一个例子为例子，假设有一个数字数组arr，现在需要查询最大的元素。

function sequentialSearch(arr) {
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

const arr = [1, 5, 9, 18, 25, 6, 12];
const max = sequentialSearch(arr);
console.log('最大元素为', max); // 输出25

在上面的例子中，我们使用了一个变量max来保存当前已经遍历过的元素中的最大值，然后逐个比较，如果找到更大的就更新max，最终返回max。

Tags: