好吧,你的代码中有一些小错误.要找到它们,您应该使用调试器,或者至少添加跟踪以了解发生的情况.这是您的原始代码,其中包含使问题显而易见的痕迹：
def search(list, target):
min = 0
max = len(list)-1
avg = (min+max)/2
print list, target, avg
...
你可以立即看到：
>你搜索一个子阵列,当你低于平均值时跳过avg-1
>当您在子数组中搜索时,您将获得该子数组中的索引
修复现在是微不足道的：
elif (list[avg] < target):
return avg + 1 + search(list[avg+1:], target) # add the offset
else:
return search(list[:avg], target) # sublist ends below the upper limit
这不是全部,当你以min == max结束循环时,你不返回任何东西(意味着你返回None).最后但并非最不重要的是,永远不要使用标准Python库中的名称来表示您自己的变量.
所以这是固定代码：
def search(lst, target):
min = 0
max = len(lst)-1
avg = (min+max)/2
# uncomment next line for traces
# print lst, target, avg
while (min < max):
if (lst[avg] == target):
return avg
elif (lst[avg] < target):
return avg + 1 + search(lst[avg+1:], target)
else:
return search(lst[:avg], target)
# avg may be a partial offset so no need to print it here
# print "The location of the number in the array is", avg
return avg