Python搜索算法详解（从零开始掌握线性搜索与二分搜索）

1. 线性搜索（Linear Search）

线性搜索是最简单直观的搜索方法。它从数据结构的第一个元素开始，逐个检查每个元素，直到找到目标值或遍历完整个列表。

优点：适用于任何顺序的数据（无需排序）。
缺点：效率较低，时间复杂度为 O(n)。

Python 实现线性搜索

def linear_search(arr, target):    """    在列表 arr 中线性搜索 target    返回目标元素的索引，若未找到则返回 -1    """    for i in range(len(arr)):        if arr[i] == target:            return i    return -1# 示例使用numbers = [10, 25, 3, 47, 15, 8]result = linear_search(numbers, 47)if result != -1:    print(f"找到目标，索引为: {result}")else:    print("未找到目标")

2. 二分搜索（Binary Search）

二分搜索是一种高效的搜索算法，但要求数据必须是已排序的。它通过不断将搜索范围缩小一半来快速定位目标元素。

优点：效率高，时间复杂度仅为 O(log n)。
缺点：仅适用于有序数据。

Python 实现二分搜索（递归版）

def binary_search_recursive(arr, target, low, high):    """    递归实现二分搜索    arr: 已排序的列表    target: 要查找的目标值    low, high: 搜索范围的起始和结束索引    """    if low > high:        return -1  # 未找到    mid = (low + high) // 2    if arr[mid] == target:        return mid    elif arr[mid] > target:        return binary_search_recursive(arr, target, low, mid - 1)    else:        return binary_search_recursive(arr, target, mid + 1, high)# 示例使用sorted_numbers = [3, 8, 10, 15, 25, 47]result = binary_search_recursive(sorted_numbers, 15, 0, len(sorted_numbers) - 1)if result != -1:    print(f"找到目标，索引为: {result}")else:    print("未找到目标")

Python 实现二分搜索（迭代版）

def binary_search_iterative(arr, target):    """    迭代实现二分搜索    """    low, high = 0, len(arr) - 1    while low <= high:        mid = (low + high) // 2        if arr[mid] == target:            return mid        elif arr[mid] > target:            high = mid - 1        else:            low = mid + 1    return -1# 示例使用sorted_numbers = [3, 8, 10, 15, 25, 47]result = binary_search_iterative(sorted_numbers, 25)if result != -1:    print(f"找到目标，索引为: {result}")else:    print("未找到目标")

如何选择合适的搜索算法？

• 如果你的数据是无序的，或者数据量很小（比如少于100个元素），使用线性搜索即可。
• 如果你的数据是已排序的，并且数据量较大，强烈推荐使用二分搜索以获得更高的效率。
• 在实际项目中，Python 内置的 in 操作符底层使用的是线性搜索，而 bisect 模块提供了高效的二分搜索工具。

总结

通过本教程，你已经掌握了两种基础但极其重要的Python搜索算法：线性搜索和二分搜索。无论你是准备面试，还是开发实际应用，这些知识都将为你打下坚实的基础。记住，算法入门教程的关键在于理解原理并动手实践——多写几遍代码，你会越来越熟练！

继续学习更多数据结构与算法，开启你的编程高手之路吧！