使用递归编写 BinarySearch 方法时出现 IndexError

Question

def binarySearch2(arr, val):
    left = 0
    right = len(arr) - 1
    mid = (left + right) // 2
    arr.sort()
    if val == arr[mid]:
        return True
    if val > arr[mid]:
        return binarySearch2(arr[mid + 1:], val)
    if val < arr[mid]:
        return binarySearch2(arr[:mid - 1], val)


    for i in range(10):
        print(binarySearch2([1, 2, 3, 4, 5, 6, 7, 8, 9], i))

它一直告诉我索引超出范围，我不确定哪里出了问题。

Answer 1

噢，你错过了 2 件愚蠢的事情，看看下面的函数

def binarySearch2(arr=[1, 2, 6], val=4):
left = 0
right = len(arr) - 1
mid = (left + right) // 2

# Base condition: If the left index crosses the right index, return False
if left > right:
    return False
arr.sort()

if val == arr[mid]:
    return True
if val > arr[mid]:
    return binarySearch2(arr[mid + 1:], val)
# If the value is less than the middle element, search the left half
if val < arr[mid]:
    return binarySearch2(arr[:mid], val)

第一个错误：我们知道，递归总是有一个基本条件，否则会引发错误（超出最大递归深度）。 所以，我们在这里添加了

if left > right:
    return False
# This is the base condition here

第二个错误：

if val < arr[mid]:
   return binarySearch2(arr[:mid - 1], val)
   # Here, you don't need the -1. I would like to give you an example,
# This is for understanding the right limit

list(range(1,10))
# Result is [1, 2, 3, 4, 5, 6, 7, 8, 9]
# We know, the right limit is always less by 1

我想现在困惑已经消除了，如果您还有更多问题要问，请随时询问。我很乐意提供帮助。