博客

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

顺序查找算法详解

顺序查找也叫线性查找，是一种基本的查找方法，其基本思想是从头到尾依次扫描列表中的每一个元素，直到找到目标元素，或者没有找到目标元素。顺序查找适用于数据量较小的列表查找，但是数据量太大时，它的效率较低。概括来说，顺序查找算法的时间复杂度是O(n)。

顺序查找算法的代码如下：

def seq_search(arr, val):
    """
    顺序查找算法：在列表 arr 中查找值为 val 的元素，返回该元素在列表中第一次出现的下标。
    如未找到，则返回 -1。
    """
    for i in range(len(arr)):
        if arr[i] == val:
            return i
    return -1

顺序查找的使用方法

步骤一：导入函数

在使用顺序查找算法之前，需要导入该函数。

from seq_search import seq_search

步骤二：定义列表

接着定义一个列表，我们将在这个列表中查找某个元素。

arr = [1, 3, 5, 7, 9, 11, 13]

步骤三：查找元素

使用顺序查找算法查找某个元素，例如查找值为 9 的元素。

pos = seq_search(arr, 9)

if pos == -1:
    print("元素不存在")
else:
    print(f"元素在列表中的下标为 {pos}")

输出结果为：

元素在列表中的下标为 4

示例一：查找学生信息

下面我们来看一个实际的例子，如何使用顺序查找算法查找学生信息。

students = [
    {'id': '001', 'name': '小明'},
    {'id': '002', 'name': '小红'},
    {'id': '003', 'name': '小张'},
    {'id': '004', 'name': '小李'},
]

def find_student(id):
    """
    在学生列表 students 中查找学号为 id 的学生，返回该学生的姓名。
    如未找到，则返回空字符串。
    """
    for stu in students:
        if stu['id'] == id:
            return stu['name']
    return ''

我们来测试一下 find_student 函数是否可以正确查找学生信息。在函数之后，我们可以这样调用：

name = find_student('002')

if name == '':
    print("该学生不存在")
else:
    print(f"查找到的学生姓名为 {name}")

输出结果为：

查找到的学生姓名为 小红

示例二：查找字符串

下面再来看一个简单的例子，如何使用顺序查找算法在字符串中查找某个字符。

def find_char(string, char):
    """
    在字符串 string 中查找字符 char，返回该字符第一次出现的下标。
    如未找到，则返回 -1。
    """
    for i in range(len(string)):
        if string[i] == char:
            return i
    return -1

我们来测试一下 find_char 函数是否可以正确查找字符

pos = find_char('Hello, World!', 'o')

if pos == -1:
    print("字符不存在")
else:
    print(f"字符在字符串中的下标为 {pos}")

输出结果为：

字符在字符串中的下标为 4

顺序查找算法是一种简单有效的查找方法，尤其适用于数据量较小的情境。

Tags: