完善def binary_search(lst,value,lower,upper)
时间: 2023-10-16 09:08:14 浏览: 50
当我们使用二分查找时,我们通常需要知道查找范围的上下界。因此,我们可以使用一个函数 `binary_search` 来实现二分查找,该函数接受四个参数:
- `lst`:一个有序数组
- `value`:要查找的值
- `lower`:查找范围的下界
- `upper`:查找范围的上界
下面是完善后的 `binary_search` 函数的代码:
```python
def binary_search(lst, value, lower, upper):
"""
在有序列表 lst 中查找值为 value 的元素,并返回其下标,如果不存在则返回 -1。
查找范围为 [lower, upper]。
"""
if lower > upper:
return -1
mid = (lower + upper) // 2
if lst[mid] == value:
return mid
elif lst[mid] < value:
return binary_search(lst, value, mid + 1, upper)
else:
return binary_search(lst, value, lower, mid - 1)
```
该函数首先检查下界是否大于上界,如果是,则返回 -1。然后,函数计算中间位置 `mid`,如果中间位置的元素等于要查找的值,则返回 `mid`。如果中间位置的元素小于要查找的值,则在右半部分继续查找。否则,在左半部分继续查找。
使用该函数时,我们可以调用 `binary_search(lst, value, 0, len(lst) - 1)` 来查找一个有序数组 `lst` 中是否存在值为 `value` 的元素,查找范围为整个数组。
该函数的时间复杂度为 O(log n),空间复杂度为 O(log n)(递归调用栈的深度为 log n)。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)