根据二分查找策略,写一个二分查找的递归过程。
时间: 2024-03-26 08:33:19 浏览: 38
二分查找是一种常用的查找算法,它将查找范围逐渐缩小一半来快速定位目标元素。下面是一个使用递归方式实现的二分查找过程:
```python
def binary_search_recursive(arr, target, low, high):
if low > high:
return -1 # 未找到目标元素
mid = (low + high) // 2
if arr[mid] == target:
return mid # 找到目标元素
if arr[mid] > target:
return binary_search_recursive(arr, target, low, mid - 1) # 在左半部分继续查找
else:
return binary_search_recursive(arr, target, mid + 1, high) # 在右半部分继续查找
```
这个递归函数接受四个参数:待查找的有序数组 `arr`、目标元素 `target`、查找范围的起始索引 `low` 和终止索引 `high`。函数首先判断 `low` 是否大于 `high`,如果是,则表示未找到目标元素,返回 -1。然后计算中间元素的索引 `mid`,如果 `arr[mid]` 等于目标元素 `target`,则返回 `mid`。如果 `arr[mid]` 大于 `target`,则在左半部分继续递归查找;如果 `arr[mid]` 小于 `target`,则在右半部分继续递归查找。
使用该递归函数可以在有序数组中查找目标元素的索引。如果找到目标元素,返回其索引;如果未找到,返回 -1。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)
![](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)
![](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)