python 假设已有列表a,其n个数值型元素已经从小到大排序完成。现输入另一数值x,现要求使用递归的二分法搜索x,如果x存在,则打印输出x在列表a中的下标,否则打印输出-1。
时间: 2024-02-03 14:13:54 浏览: 64
可以使用递归的二分法搜索算法来查找x是否存在于已排序的列表a中。具体实现如下:
```python
def binary_search(a, x, low, high):
if low > high:
return -1
mid = (low + high) // 2
if a[mid] == x:
return mid
elif a[mid] < x:
return binary_search(a, x, mid+1, high)
else:
return binary_search(a, x, low, mid-1)
```
其中,a为已排序的列表,x为要查找的元素,low和high分别为列表的最小和最大下标。函数首先判断low和high的大小关系,如果low大于high,则表示x不存在于列表a中,返回-1。否则,计算中间位置mid,并判断a[mid]和x的大小关系。如果a[mid]等于x,则返回mid;如果a[mid]小于x,则在列表a的右半部分继续查找;如果a[mid]大于x,则在列表a的左半部分继续查找。
可以调用该函数来查找x在列表a中的下标:
```python
a = [1, 3, 4, 7, 9, 10, 12]
x = 7
index = binary_search(a, x, 0, len(a)-1)
print(index) # 输出 3
```
如果x不存在于列表a中,则返回-1:
```python
a = [1, 3, 4, 7, 9, 10, 12]
x = 5
index = binary_search(a, x, 0, len(a)-1)
print(index) # 输出 -1
```
阅读全文