以下是一个使用 **Python** 实现的 **二分查找（Binary Search）** 算法示例，包含 **递归** 和 **迭代** 两种版本。该算法用于在 **有序列表** 中高效查找目标值的位置。 --- ### 🧠 算法思想 **二分查找** 是一种经典的 **分治算法（Divide and Conquer）**，其核心思想是： 1. 比较中间元素与目标值。 2. 如果相等，返回索引。 3. 如果目标值小于中间元素，在左半部分继续查找。 4. 如果目标值大于中间元素，在右半部分继续查找。 5. 重复上述步骤，直到找到目标或搜索范围为空。 --- ### 🧾 代码实现 ```python def binary_search_recursive(arr, target, low=0, high=None): """ 使用递归实现二分查找。 参数: arr (list): 已排序的整数列表（升序） target (int): 要查找的目标值 low (int): 当前搜索范围的起始索引（默认为0） high (int): 当前搜索范围的结束索引（默认为列表末尾） 返回: int: 目标值在列表中的索引，若未找到则返回 -1 """ if high is None: high = len(arr) - 1 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, mid + 1, high) # 在右半部分查找 else: return binary_search_recursive(arr, target, low, mid - 1) # 在左半部分查找 def binary_search_iterative(arr, target): """ 使用迭代实现二分查找。 参数: arr (list): 已排序的整数列表（升序） target (int): 要查找的目标值 返回: int: 目标值在列表中的索引，若未找到则返回 -1 """ low = 0 high = len(arr) - 1 while low <= high: mid = (low + high) // 2 if arr[mid] == target: return mid elif arr[mid] < target: low = mid + 1 # 在右半部分查找 else: high = mid - 1 # 在左半部分查找 return -1 # 未找到目标值 # 示例：测试二分查找函数 if __name__ == "__main__": sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] target = 11 # 使用递归版本 index_recursive = binary_search_recursive(sorted_list, target) print(f"递归查找结果：目标 {target} 的索引为 {index_recursive}") # 使用迭代版本 index_iterative = binary_search_iterative(sorted_list, target) print(f"迭代查找结果：目标 {target} 的索引为 {index_iterative}") ``` --- ### 📌 示例输出 ``` 递归查找结果：目标 11 的索引为 5 迭代查找结果：目标 11 的索引为 5 ``` --- ### 📝 说明 - **时间复杂度**：`O(log n)`，比线性查找快得多。 - **空间复杂度**： - 递归版本：`O(log n)`（调用栈开销） - 迭代版本：`O(1)`（原地操作，无额外空间） - **适用场景**： - 数据已排序。 - 需要快速查找。 - 迭代版本更适合大规模数据或内存敏感场景。 --- ### ✅ 小贴士 - 使用二分查找前，**必须确保列表已排序**。 - 二分查找常用于： - 查找元素是否存在。 - 寻找插入位置（如 `bisect` 模块）。 - 解决“最接近的值”、“第一个大于等于目标的值”等变体问题。 --- 如果你希望看到 **字符串处理**、**文件读写**、**图形界面** 或 **网络请求** 等示例，也可以告诉我，我可以继续为你编写！