二分查找python递归版
时间: 2023-09-22 18:06:15 浏览: 50
### 回答1:
当然可以,下面是一个简单的例子:
```python
def binary_search(arr, low, high, target):
if high >= low:
mid = (high + low) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, low, mid - 1, target)
else:
return binary_search(arr, mid + 1, high, target)
else:
return -1
```
其中,`arr` 是要查找的有序数组,`low` 和 `high` 分别是数组的起始位置和结束位置,`target` 是要查找的值。函数首先计算出中间位置 `mid`,然后比较 `arr[mid]` 和 `target` 的大小,如果相等则返回 `mid`,否则根据大小关系递归地在左半部分或右半部分继续查找。如果数组中不存在目标值,则返回 `-1`。
### 回答2:
二分查找是一种高效的查找算法,它的思想是将有序列表分成两部分,通过比较目标值与中间元素的大小,确定目标值所在子列表的位置,然后再在该子列表中进行查找。以下是二分查找的递归版的Python实现:
```python
def binary_search_recursive(arr, target, start, end):
if start > end:
return -1
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search_recursive(arr, target, start, mid-1)
else:
return binary_search_recursive(arr, target, mid+1, end)
```
函数接受四个参数,分别是有序列表arr、目标值target、列表的起始索引start,以及列表的结束索引end。首先,判断列表是否为空,如果起始索引start大于结束索引end,则说明目标值不在列表中,返回-1。接下来,计算中间索引mid,并将中间元素与目标值进行比较。如果相等,则找到了目标值,返回中间索引。如果中间元素大于目标值,则在左边的子列表中进行递归查找。如果中间元素小于目标值,则在右边的子列表中进行递归查找。
通过递归调用,直到找到目标值或者确认目标值不存在。这种递归方法的时间复杂度是O(log n),因为每次查找都将列表规模缩小一半。
### 回答3:
二分查找是一种用于在有序数组中查找特定元素的算法。其思想是首先找到数组的中间元素,然后将待查找的元素与中间元素进行比较,如果相等,则返回中间元素的索引;如果待查找元素比中间元素小,则在数组的左半部分继续进行二分查找;如果待查找元素比中间元素大,则在数组的右半部分继续进行二分查找,直至找到目标元素或者确定目标元素不存在。
下面是Python中的递归版二分查找算法实现:
```python
def binary_search(arr, target, low, high):
if low > high:
return -1 # 如果low大于high,表示数组为空,返回-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`表示数组的结束索引。函数通过比较中间元素来缩小查找范围,直到找到目标元素或者确定目标元素不存在。
使用该函数进行二分查找时,需要首先对数组进行排序,然后调用`binary_search`函数,并传入待查找的数组、目标元素、起始索引和结束索引。函数将返回目标元素的索引,如果未找到目标元素,则返回-1表示未找到。