递归二进制搜索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

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

if (val > mid):

你应该说

if (val > arr[mid]):

由于您要比较的是值而不是索引。

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

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

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

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)