我一直想进行二进制搜索(通过递归),但我不知道为什么我的代码不起作用... 任何人都可以请更正我的代码并说明它不起作用的原因吗??
正如您在我的代码中看到的那样,我在每次递归时对字符串进行切片,最后当找到目标时,我将返回目标的位置..
def binary(n,target):
n.sort()
mid = (0 + (len(n)-1))//2
if target == n[mid]:
return mid
elif target < n[mid]:
return binary(n[:mid],target)
elif target > n[mid]:
return binary(n[mid:],target)
这是我收到的错误信息... RecursionError:调用 Python 对象时超出最大递归深度。
请您参考如下方法:
有两个问题,都在最后一行:
def binary(n, target):
n.sort()
mid = (0 + (len(n) - 1)) // 2
if target == n[mid]:
return mid
elif target < n[mid]:
return binary(n[:mid], target)
elif target > n[mid]:
return mid + 1 + binary(n[mid + 1:],target)
^^^^^^^^ ^
- 由于您正在切片,并且为了在原始排序列表中提供索引,我们需要跟踪我们在递归时“丢失”的索引
n[:mid]的完整形式是n[mid+1:]- 而不是n[mid:]因为你已经检查目标(在中间)并希望将其从 future 的迭代中删除 - 顺便说一下,这是导致无限循环的原因!
由于我们在 mid+1 处对列表进行切片,因此我们需要在递归调用之前添加 mid+1,以便保留列表右侧的项目索引:
[1,2,3,4,5]
^ say we slice here and get [4,5]
we want to save the indexes so we'll add mid (2) + 1 since now in [4,5] the item 4 will get the index zero
评论:通过在每次迭代时调用 n.sort(),我们“失去”了二进制搜索的所有优势,因为即使在列表排序之后,重新排序也至少需要在)。因此,如果我们需要先排序,我们不妨迭代数组直到找到/找不到该项目。或者,如果我们坚持排序,只做一次,然后才递归调用:
n.sort()
binary(n, 2)
binary 不再包含排序:
def binary(n, target):
mid = (0 + (len(n) - 1)) // 2
if target == n[mid]:
return mid
elif target < n[mid]:
return binary(n[:mid], target)
elif target > n[mid]:
return mid + 1 + binary(n[mid + 1:], target)
