递归二叉搜索蟒蛇

Question

我一直在尝试递归编写二进制搜索。当我使用 list[：] 语法执行此操作时，我没有得到预期的结果，出现几个错误或没有得到正确的值。

def binary_search(arr, val):
left = 0 
right = len(arr)-1
mid = (left + right)//2
#Go through the array
if (val == arr[mid]):
return mid
#Check right side of arr
if (val > arr[mid]):
return binary_search(arr[mid+1:], val)
#Check left side of arr
return binary_search(arr[:mid], val)

编辑：示例输入和输出

arr1 =[]
for i in range(10):
arr1.append(i)
for i in range(10):
print(binary_search(arr1,i))

我希望得到类似'0,1,2,3,4,5,6,7,8,9'的东西，但得到'0,1,0,0,4,None ,None,2,0,0'

Answer 1

你有两个问题。第一个是错别字，你说

if (val > mid):

你应该说

if (val > arr[mid]):

因为您比较的是值而不是索引。

第二个更微妙...当您检查数组的右侧时，在：

return binary_search(arr[mid+1:], val)

您传递给递归调用 (arr[mid+1:]( 的子数组已经在数组的中间开始，这意味着该递归调用的结果将返回子数组中元素的索引。 因此，您需要添加用于拆分数组的索引增量，以再次获得基于完整数组的索引：

return binary_search(arr[mid+1:], val) + (mid + 1)

以下是完整性的完整代码：

def binary_search(arr, val):
left = 0 
right = len(arr)-1
mid = (left + right)//2
#Go through the array
if (val == arr[mid]):
return mid
#Check right side of arr
if (val > arr[mid]):
return binary_search(arr[mid+1:], val) + (mid + 1)
#Check left side of arr
return binary_search(arr[:mid], val)

Answer 2

您正在将val与mid进行比较，而不是与arr[mid]进行比较。此外，如果您使ifs相互排斥，它会更好读。此外，根据下面nosklo的答案，您需要为大于情况添加索引偏移量：

#Go through the array
if (val == arr[mid]):
return mid
#Check right side of arr
elif (val > mid):
return binary_search(arr[mid+1:], val) + (mid + 1)
#Check left side of arr
else:
return binary_search(arr[:mid], val)

Answer 3

这里，更通用的二叉搜索递归函数，如果未找到键，则返回None。

def binary_search(arr, val):
mid = len(arr) // 2
if (val == arr[mid]):
return mid
if mid == 0:
return None
if (val > arr[mid]):
call_back = binary_search(arr[mid+1:], val)
return call_back + mid + 1 if call_back is not None else None
return binary_search(arr[:mid], val)

结果：

arr = list(range(10))
for i in range(15):
print(binary_search(arr, i))

0
1
2
3
4
5
6
7
8
9
None
None
None
None
None