python请用递归来实现二分法查找要求
时间: 2023-06-20 18:06:02 浏览: 45
好的,以下是使用递归实现二分法查找的 Python 代码:
```python
def binary_search(arr, target, low, high):
"""
递归实现二分法查找
:param arr: 有序数组
:param target: 查找目标
:param low: 数组起始下标
:param high: 数组结束下标
:return: 目标下标,不存在则返回-1
"""
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, low, mid - 1)
else:
return binary_search(arr, target, mid + 1, high)
```
其中,`arr` 为有序数组,`target` 为查找的目标值,`low` 和 `high` 分别为数组的起始下标和结束下标。首先判断 `low` 是否大于 `high`,如果是,则返回 `-1` 表示未找到目标值。否则,计算 `mid = (low + high) // 2`,如果 `arr[mid] == target`,则直接返回 `mid`;如果 `arr[mid] > target`,则说明目标值在左侧区间,递归调用 `binary_search(arr, target, low, mid - 1)`;如果 `arr[mid] < target`,则说明目标值在右侧区间,递归调用 `binary_search(arr, target, mid + 1, high)`,最终返回目标下标或 `-1`。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)