算法实习：使用 Python 的线性搜索 😎

Source: Dev.to

什么是线性搜索？ 🤔

线性搜索是一种在列表（list）中查找某个值（称为 target）的方法，它会 从头到尾逐个检查元素。

• 找到 → 返回它的位置（索引）。
• 没找到 → 返回 “没有！”（通常返回 -1）。

优点： 超级简单，不要求列表有序。
缺点： 当列表非常长时会很慢（如果目标在末尾或不存在，需要检查所有元素）。

上图展示了线性搜索的工作方式：从索引 0 开始，逐个检查直到找到目标。

线性搜索的逐步工作原理 📝

假设我们的列表是：[10, 20, 30, 40, 50]，目标是：30

1. 从索引 0 开始：10 == 30？否。
2. 索引 1：20 == 30？否。
3. 索引 2：30 == 30？是！在位置 2 找到。

如果目标是 60：检查到最后仍未找到 → 返回未找到。

这张图更详细地展示了每一步，就像侦探在找失踪的物品！ 🕵️‍♂️

Python 实现 🐍

我们编写一个名为 linear_search 的简单函数。

def linear_search(arr, target):
    for i in range(len(arr)):          # Loop 从 0 到列表长度 - 1
        if arr[i] == target:           # 如果第 i 个元素等于目标
            return i                   # 返回它的索引
    return -1                          # 循环结束仍未找到，返回 -1

示例 1：在整数列表中查找数字 👍

daftar_angka = [15, 7, 23, 42, 9, 31]
target = 23

hasil = linear_search(daftar_angka, target)
if hasil != -1:
    print(f"Ketemu! {target} ada di index {hasil}")
else:
    print(f"{target} nggak ada di list 😢")

输出： Ketemu! 23 ada di index 2

示例 2：在字符串列表（水果名）中查找字符

daftar_buah = ["Apel", "Pisang", "Jeruk", "Mangga", "Durian"]
target = "Mangga"

hasil = linear_search(daftar_buah, target)
if hasil != -1:
    print(f"Yummy! {target} ada di urutan ke-{hasil + 1} (index {hasil})")
else:
    print("Buahnya habis stok 😭")

输出： Yummy! Mangga ada di urutan ke-4 (index 3)

示例 3：未找到（返回 -1）

daftar_hewan = ["Kucing", "Anjing", "Kelinci", "Burung"]
target = "Singa"

hasil = linear_search(daftar_hewan, target)
if hasil != -1:
    print(f"Ketemu hewan {target}!")
else:
    print(f"{target} nggak ada di kebun binatang ini 🦁")

输出： Singa nggak ada di kebun binatang ini 🦁

示例 4：空列表或目标在开头/结尾

# 目标在开头
list1 = [100, 200, 300]
print(linear_search(list1, 100))   # 输出: 0

# 目标在结尾
print(linear_search(list1, 300))   # 输出: 2

# 空列表
list_kosong = []
print(linear_search(list_kosong, 5))   # 输出: -1

进阶：与二分搜索比较 🔍

线性搜索适用于小规模或无序的列表。如果列表已经排好序，使用二分搜索会更快（就像从字典中间翻页查找）。

图中展示了两者的区别：线性搜索遍历全部，二分搜索每次把搜索范围减半。

给你的练习！ 💪

• 修改代码，使函数返回目标出现的次数（如果有重复）。
• 为你的朋友名单实现线性搜索，并搜索自己的名字。
• 进行计时实验：使用一个大列表（例如 1000 个元素），并用 time 模块测量运行时间。

祝你实战练习愉快！如果已经掌握线性搜索，你已经离成为优秀程序员更进一步了。有什么不明白的，随时提问或自己动手实验。玩得开心，编码愉快！ 🎉🐍