线性查找和二分查找的示例任务

3.1 使用线性查找在数组中找到元素的任务

任务： 给定一个数字数组。需要使用线性查找找到指定数字的索引。如果未找到数字，则返回-1。

示例：

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -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

说明：

• 函数linear_search 遍历数组 arr 中的每个元素并与 target 进行比较。
• 如果找到元素，则返回其索引。
• 如果所有元素都检查完且未找到目标值，则函数返回-1。

逐步执行：

1. 数组 [4, 2, 7, 1, 9, 3] 和目标值 7。
2. 开始搜索：比较第一个元素 (4) 与 7 — 不匹配。
3. 移至下一个元素 (2) — 不匹配。
4. 移至下一个元素 (7) — 匹配。
5. 返回索引 2。

3.2 使用二分查找在排序数组中找到元素的任务

任务： 给定一个排序的数字数组。需要使用二分查找找到指定数字的索引。如果未找到数字，则返回-1。

示例：

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 示例使用：
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"元素 {target} 找到在索引 {result}")  # 输出: 元素 7 找到在索引 3

# 示例使用对于不存在的元素：
target = 6
result = binary_search(sorted_array, target)
print(f"元素 {target} 找到在索引 {result}")  # 输出: 元素 6 找到在索引 -1

说明：

• 函数 binary_search 使用两个指针 (left 和 right) 来跟踪数组 arr 中搜索的边界。
• 在每次迭代中，找到数组的中间元素并与 target 进行比较。
• 如果中间元素等于 target，则返回其索引。
• 如果 target 小于中间元素，则在数组的左半部分继续搜索。
• 如果 target 大于中间元素，则在数组的右半部分继续搜索。
• 如果边界交叉且未找到元素，则返回-1。

逐步执行：

1. 排序数组 [1, 3, 5, 7, 9, 11, 13] 和目标值 7。
2. 初始搜索边界：left = 0, right = 6。
3. 找到中间元素：mid = (0 + 6) // 2 = 3。
4. 比较中间元素 (7) 与 target (7) — 匹配。
5. 返回索引 3。

3.3 比较并选择适合不同任务的搜索算法

线性搜索与二分搜索的比较：

选择合适的搜索算法

线性查找：

• 用于数据未排序时。
• 适用于小数组或列表。
• 当元素数量不多且操作时间不关键时使用。

二分查找：

• 用于数据已排序时。
• 适合大数组，查找速度很重要时。
• 在同一数据集进行频繁查找时非常有效 (数据可以预排序)。

3.4 巩固材料的练习任务

任务1：线性查找

给定一个数字数组。编写一个函数来使用线性查找查找指定的数字。函数应返回找到的元素的索引或-1，如果未找到元素。

示例：

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

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

# 额外测试：
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

任务2：二分查找

给定一个排序的数字数组。编写一个函数来使用二分查找查找指定的数字。函数应返回找到的元素的索引或-1，如果未找到元素。

示例：

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 示例使用：
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"元素 {target} 找到在索引 {result}")  # 输出: 元素 7 找到在索引 3

# 额外测试：
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

任务3：线性搜索和二分搜索的比较

给定一个数字数组。编写两个函数来查找指定的数字：一个使用线性查找，另一个使用二分查找。在大数组上比较两个函数的性能。

示例：

import time
import random

# 线性查找
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# 二分查找
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 生成大数组
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# 性能比较
start_time = time.time()
linear_search(large_array, target)
print(f"线性查找耗时: {time.time() - start_time:.6f} 秒")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"二分查找耗时: {time.time() - start_time:.6f} 秒")