Python中二进制搜索的递归方法

Question

我现在正在学习算法，并对二进制搜索的递归方法有一个问题。我试着自己编码如下：

def binary_search_rec(x, value):
x.sort()
length = len(x)
if length == 1 and x[0] == value:
return 0
elif length == 1 and x[0] != value:
return 'none'
else:
low = 0 
high = length - 1
mid = (low + high)//2
if value == x[mid]:
return mid
elif value > x[mid]:
return mid + binary_search_rec(x[mid+1:], value)
else:
return binary_search_rec(x[0:mid], value)

基本情况是具有单个元素的数组。然而，我无法收到玩具数据的正确结果：

binary_search_rec([1, 2, 3, 4], 3)

其将返回CCD_ 1。

你能帮我找出我哪里做错了吗？提前感谢您的帮助。

Answer 1

此代码可能会帮助您，基于您的代码，我有一些修改。

def binary_search_rec(x, value):
x.sort()
length = len(x)
if length==0 or length ==None:
return -float('inf')
elif length == 1 and x[0] == value:
return 0
elif length == 1 and x[0] != value:
return -float('inf')
else:
low = 0 
high = length - 1
mid = (low + (high-low))//2
if value == x[mid]:
return mid
elif value > x[mid]:
return mid + 1 + binary_search_rec(x[mid+1:], value)
else:
return binary_search_rec(x[0:mid+1], value)
print(binary_search_rec([1, 2, 3, 4, 5], 3))

输出：2(索引(

不过，字符串返回"none"不是一个好主意，您可以返回inf值，而不是返回"none"。

Answer 2

如果您想使用递归方法返回找到的数字的索引，则需要跟踪相对于初始列表的索引。将切片传递回递归将返回相对于该切片的索引，这不是正确的答案。一种更简单的方法是将低值和高值和原始列表一起传递到递归中，而不是切片。您可以使用默认值处理此问题，这样就不会给调用者带来计算负担。这将更容易推理，也更快，因为您不会在每次递归调用中分配列表切片的新副本。例如：

def binary_search_rec(x, value, low = 0, high = None):
if high is None:
high = len(x) 
# edge case -- we didn't find it
if high <= low :
return 'none'
# the mid is relative to the whole list, so add low to it
mid = (high - low) // 2 + low   
if value == x[mid]:
return mid 
elif value > x[mid]:
return binary_search_rec(x, value, mid + 1, high)
else:
return binary_search_rec(x, value, low, mid)

for i in range(8):
print(binary_search_rec([1, 2, 3, 4, 5, 6], i))

打印：

none
0
1
2
3
4
5
none

此外，如果返回索引，则对输入进行排序是没有意义的——您应该期望调用方传递经过排序的输入。如果调用者传递binary_search_rec([3, 2, 1], 1)，而您返回0，因为这是排序列表的索引，那么这对调用者没有真正的帮助。