最大呼叫堆栈超过了二进制搜索python

Question

我正在尝试用Python 递归实现二分查找。

我在上面编写代码：

space = [i for i in range(4096)]

# Recursive:
def binarySearchRec(arr, low, high, target):
    if high >= low:
        mid = (high + low) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binarySearchRec(arr, low, mid-1, target)
        else:
            return binarySearchRec(arr, mid, high, target)
    else:
        return -1

if __name__ == '__main__':
    element = random.choice(space)
    print(f"Index: {binarySearchRec(space, 0, len(space)-1, element)} | Number: {element}")

这应该在最多 12 个步骤中返回答案，因为复杂度为 O(log(N))。但有些运行它超出了最大调用堆栈。我怎样才能防止这种情况发生，我找不到原因。

我将非常感谢您的答复。

大家好，谢谢您的回答，

我也找到了问题的解决方案。每次目标>到达[中] 我返回的是低=中。我将其更改为 low = mid + 1。

这解决了问题，并且它的工作方式与预期的 13 个步骤中找到的最后一个元素相反。

代码：

def binarySearchRec(arr, low, high, target):
    if high >= low:
        mid = (high + low) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binarySearchRec(arr, low, mid-1, target)
        else:
            return binarySearchRec(arr, mid+1, high, target)
    else:
        return -1

Answer 1

您的功能有效，除非可变“高”高于“低”的情况，并且目标等于高变量。这是因为高＆gt; = low是正确的，但是中间至低，这不等于目标。您可以添加：

if high - 1 == low:
    if arr[low] == target:
        return low
    return high

如果高＆gt; = low： line之前或之后。另外，您无需调用arr [x]，因为arr [x] == x，所以arr [x]对x进行评估，您可以替换它。

Answer 2

在此类问题中，相差一错误很难调试。您有两个问题 -

1. 当 target 小于 arr[mid] 时，子问题是 low, mid
2. 当 target< /code> 大于 arr[mid]，子问题是 mid + 1, high

我发现编写 < 有帮助> 条件和 > 条件。如果这两个条件都不满足，则 == 默认为 else 条件。

def binary_search(arr, target, low, high):
  if low >= high:
    return -1
  else:
    mid = (low + high) // 2
    if target < arr[mid]:
      return binary_search(arr, target, low, mid)       #1
    elif target > arr[mid]:
      return binary_search(arr, target, mid + 1, high)  #2
    else:
      return mid                                        # target == arr[mid]

def search(sorted_arr, q):
  return binary_search(sorted_arr, q, 0, len(sorted_arr))

foo = list(range(1000000))
print(search(foo, 523407))

523407

请注意，对于此特定问题，您不必将 range 扩展为 list。如果您实际上正在搜索范围，这可以节省大量内存。这是因为 Python 范围允许您直接使用 [] 访问元素，就像列表一样 -

bar = range(1000000)
print(search(bar, 683495)) # pass in range directly

683495