递归二分查找 python

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

您将 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 2

你有两个问题。第一个打错了，你说的是

if (val > mid):

你应该说

if (val > arr[mid]):

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

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

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

您传递给递归调用 (arr[mid+1:]) 的子数组已经从数组的中间开始，这意味着该递归调用的结果将 return 元素的索引在子数组中。所以你需要添加你用来分割数组的索引增量，再次有一个基于完整数组的索引：

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)

递归二分查找 python

Recursive binary search python

python

binary-search