顺序查找算法详解
顺序查找也叫线性查找,是一种基本的查找方法,其基本思想是从头到尾依次扫描列表中的每一个元素,直到找到目标元素,或者没有找到目标元素。顺序查找适用于数据量较小的列表查找,但是数据量太大时,它的效率较低。概括来说,顺序查找算法的时间复杂度是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
顺序查找算法是一种简单有效的查找方法,尤其适用于数据量较小的情境。