请用递归和非递归两种方式编写程序实现二分法查找。并给出时间复杂度T(n)和空间复杂度S(n)的结果。 设a=[1, 4, 8, 14, 25, 26, 37]
时间: 2024-09-09 18:00:42 浏览: 30
递归和非递归两种方式实现二分查找的示例代码如下:
递归方式的二分查找:
```python
def binary_search_recursive(arr, left, right, target):
if right < left:
return -1 # 表示没有找到
mid = left + (right - left) // 2
if arr[mid] == target:
return mid # 找到目标值,返回索引
elif arr[mid] > target:
return binary_search_recursive(arr, left, mid - 1, target)
else:
return binary_search_recursive(arr, mid + 1, right, target)
```
非递归方式的二分查找:
```python
def binary_search_iterative(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 表示没有找到
```
在这两个示例中,`arr` 是待查找的数组,`left` 和 `right` 分别表示查找区间的起始和结束索引,`target` 是要查找的目标值。
时间复杂度T(n)和空间复杂度S(n)的结果:
- 递归方式的时间复杂度:T(n) = O(log n),空间复杂度:S(n) = O(log n),因为每次递归调用都会创建新的栈帧,递归深度是log n。
- 非递归方式的时间复杂度:T(n) = O(log n),空间复杂度:S(n) = O(1),因为非递归方式不需要额外的栈空间来保存函数调用的信息。