python用递归实现二分查找
时间: 2023-04-08 18:02:41 浏览: 75
可以回答这个问题。二分查找是一种常见的算法,可以用递归实现。在 Python 中,可以这样实现:
```python
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
```
其中,arr 是要查找的有序数组,low 和 high 分别是数组的起始和结束位置,x 是要查找的元素。如果找到了,返回元素在数组中的下标,否则返回 -1。
相关问题
用python递归实现二分查找
以下是使用Python递归实现二分查找的代码示例:
```python
def binarySearch(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist) // 2
if alist[midpoint] == item:
return True
else:
if item < alist[midpoint]:
return binarySearch(alist[:midpoint], item)
else:
return binarySearch(alist[midpoint + 1:], item)
```
这个函数接受一个已排序的列表和要查找的元素作为参数。如果列表为空,则返回False。否则,函数计算列表的中间点并检查该点的值是否等于要查找的元素。如果是,则返回True。否则,函数递归地调用自身来搜索列表的左半部分或右半部分,直到找到要查找的元素或确定该元素不在列表中。
使用递归实现二分查找算法
二分查找算法(Binary Search)是一种高效的查找算法,它可以在有序数组中快速查找指定元素。下面是使用递归实现二分查找算法的代码:
```python
def binary_search_recursive(arr, left, right, target):
if left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, mid + 1, right, target)
else:
return binary_search_recursive(arr, left, mid - 1, target)
else:
return -1
```
解释一下代码:
- `arr` 是一个有序的数组,`left` 和 `right` 分别表示数组的左右边界,`target` 是要查找的目标元素。
- 首先判断左右边界是否合法,如果左边界大于右边界,说明目标元素不存在于数组中,返回 -1。
- 否则计算中间位置 `mid`,如果中间位置的元素等于目标元素,直接返回 `mid`。
- 如果中间位置的元素小于目标元素,说明目标元素在右半部分,递归调用函数,在右半部分查找目标元素。
- 如果中间位置的元素大于目标元素,说明目标元素在左半部分,递归调用函数,在左半部分查找目标元素。
使用示例:
```python
arr = [1, 3, 5, 7, 9]
target = 5
index = binary_search_recursive(arr, 0, len(arr) - 1, target)
print(index) # 输出 2
```
这里在有序数组 `[1, 3, 5, 7, 9]` 中查找元素 `5`,返回的下标为 `2`。