### Python 实现线性表的二分查找 以下是基于 Python 的线性表二分查找实现，分为 **非递归方式** 和 **递归方式**： --- #### 1. 非递归方式 非递归方式利用循环逐步缩小搜索区间，直到找到目标值或确定其不存在。 ```python def binary_search_iterative(lst, target): """ 使用非递归方式进行二分查找。 参数: lst -- 已排序的待查找列表 target -- 要查找的目标值 返回: 找到时返回索引位置；未找到时返回-1。 """ low, high = 0, len(lst) - 1 while low <= high: mid = (low + high) // 2 if lst[mid] == target: return mid # 找到目标值，返回其索引位置 elif lst[mid] < target: low = mid + 1 # 目标值位于右半部分 else: high = mid - 1 # 目标值位于左半部分 return -1 # 若遍历结束仍未找到，则返回-1表示不存在该元素 ``` 这种方法的时间复杂度为 \(O(\log n)\)，其中 \(n\) 是列表长度[^1]。它通过不断调整 `low` 和 `high` 来控制当前搜索区间的范围。 --- #### 2. 递归方式 递归方式通过函数调用自身来完成每次子区间的划分操作。 ```python def binary_search_recursive(lst, target, low, high): """ 使用递归方式进行二分查找。 参数: lst -- 已排序的待查找列表 target -- 要查找的目标值 low -- 当前搜索区间的起始索引 high -- 当前搜索区间的终止索引 返回: 找到时返回索引位置；未找到时返回-1。 """ if low > high: return -1 # 基本退出条件：如果区间为空则返回-1 mid = (low + high) // 2 if lst[mid] == target: return mid # 找到目标值，返回其索引位置 elif lst[mid] < target: return binary_search_recursive(lst, target, mid + 1, high) # 搜索右半部分 else: return binary_search_recursive(lst, target, low, mid - 1) # 搜索左半部分 ``` 为了方便测试递归版本，可以定义一个辅助函数封装初始参数传递过程： ```python def binary_search_helper(lst, target): return binary_search_recursive(lst, target, 0, len(lst) - 1) ``` 递归方法同样具有 \(O(\log n)\) 的时间复杂度[^2]，但由于涉及多次函数调用栈开销，在极端情况下可能会受到最大递归深度限制的影响。 --- ### 测试代码示例 以下是一个完整的测试脚本，用于验证上述两种实现的效果： ```python if __name__ == "__main__": test_list = [1, 3, 5, 7, 9, 11, 13, 15] target_value = 7 result_iterative = binary_search_iterative(test_list, target_value) print(f"迭代法结果: {'找到' if result_iterative != -1 else '未找到'}, 索引={result_iterative}") result_recursive = binary_search_helper(test_list, target_value) print(f"递归法结果: {'找到' if result_recursive != -1 else '未找到'}, 索引={result_recursive}") ``` --- ### 总结对比两种方法的特点： | 特征 | 非递归方式 | 递归方式 | |--------------------|------------------------------------|---------------------------------| | 时间复杂度 | \(O(\log n)\) | \(O(\log n)\) | | 空间需求 | 较低 | 受限于递归调用栈 | | 编程难度 | 中等 | 稍微复杂 | 虽然两者在理论上拥有相同的渐近性能表现，但在实际应用中需考虑具体场景下的资源消耗差异。 ---