线性搜索

1.1 线性搜索的定义

线性搜索（也称为顺序搜索）是一种在列表或数组中查找元素的算法，它依次检查每个元素，直到找到匹配项或检查完所有元素。这是最简单的搜索算法，不需要对数据进行预排序。

基本原则：

• 顺序检查：算法依次遍历数组或列表中的每个元素，将其与目标值进行比较。
• 停止搜索：当找到与目标值匹配的元素时停止搜索，或者当所有元素都已检查时停止。
• 无需排序：线性搜索可以应用于未排序的数据。
• 应用：线性搜索可以应用于支持迭代的任何数据结构，包括列表和数组。

线性搜索具有时间复杂度 O(n)，其中n为数组或列表中的元素数量。在最坏的情况下，算法需要检查所有n个元素，以找到目标值或确认其不存在。

时间复杂度分析：

• 最佳情况 (Best case)：元素在第一位找到，O(1)。
• 平均情况 (Average case)：元素在中间某处找到，O(n/2)，相当于O(n)。
• 最坏情况 (Worst case)：元素在最后一位找到或不存在，O(n)。

1.2 线性搜索的逐步实现

线性搜索步骤：

• 初始化：设置搜索的起始索引（通常是零索引）。
• 顺序检查：检查列表或数组中的每个元素是否与目标值匹配。
• 结束条件：如果找到元素，则返回其索引。如果所有元素都已检查且未找到目标值，则返回特殊值（通常为-1或None）。

Python 中线性搜索的实现：

def linear_search(arr, target):
    # 遍历数组中的每个元素
    for index, element in enumerate(arr):
        # 如果当前元素等于目标值，则返回其索引
        if element == target:
            return index
    # 如果未找到元素，则返回 -1
    return -1

实现说明逐步解释：

• 循环初始化：使用带enumerate的循环，它在每次迭代中返回数组的索引和元素。
• 比较：在每次迭代中，当前元素与目标值（target）进行比较。
• 返回索引：如果当前元素等于目标值，则返回该元素的索引。
• 返回 -1：如果循环结束且未找到目标元素，则返回-1。

# 使用示例：
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"元素 {target} 在索引 {result} 找到")  # 输出: 元素 7 在索引 2 找到

# 不存在于数组中的元素使用示例：
target = 5
result = linear_search(arr, target)
print(f"元素 {target} 在索引 {result} 找到")  # 输出: 元素 5 在索引 -1 找到

1.3 用线性搜索解决的任务示例

线性搜索用于解决与在数据集合中查找元素相关的许多任务。以下是一些此类任务的示例：

任务 1: 在数组中查找元素

需要在数字数组中找到给定的数字。

示例：

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"元素 {target} 在索引 {index} 找到")  # 输出: 元素 70 在索引 3 找到

任务 2: 检查列表中是否存在元素

需要检查给定值是否存在于字符串列表中。

示例：

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"元素 {target} {'找到' if found else '未找到'}")  # 输出: 元素 cherry 找到

任务 3: 查找最小值或最大值

需要在列表中找出最小值或最大值。

示例：

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"最小值: {min_value}")  # 输出: 最小值: 2

任务 4: 查找第一次出现

查找列表中给定元素的第一次出现。

示例：

def find_first_occurrence(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"第一次出现 {target} 在索引 {index}")  # 输出: 第一次出现 2 在索引 1

任务 5: 计数元素出现次数

计数给定元素在列表中出现的次数。

示例：

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"元素 {target} 出现 {count} 次")  # 输出: 元素 2 出现 3 次