使用二进制搜索返回目标索引

Question

我必须返回数组的目标元素的索引.

目前,当我搜索位于中点的元素时,它返回正确的索引,但对于任何其他元素,它对我不起作用.

当我溢出阵列时,我想我犯了一个错误

aList = [1,3,5,6,8,9,10,12,34,56,78,456]
def recursiveBinarySearch(aList, target):
    #aList = sorted(aList)

    if len(aList) == 0:
        return False
    else:
        midpoint = len(aList) // 2
        if aList[midpoint] == target:
            return aList.index(target)
        else:
            if target < aList[midpoint]:
                return recursiveBinarySearch(aList[:midpoint],target)
            else:
                return recursiveBinarySearch(aList[midpoint+1:],target)

print(recursiveBinarySearch(aList,9))

Answer 1

这是因为每次您进行递归调用时，都会传递一个不同的修改列表，并且每次调用中的索引都会更改。例如，如果您在数组的后半部分搜索数字，则最终返回的值将小于，len(aList)/2因为在下次迭代中仅传递数组的这一部分。

解决方法是传递start和end指向列表，而不是拆分列表。

aList = [1,3,5,6,8,9,10,12,34,56,78,456]
def recursiveBinarySearch(aList, target, start, end):
    #aList = sorted(aList)

    if end-start+1 <= 0:
        return False
    else:
        midpoint = start + (end - start) // 2
        if aList[midpoint] == target:
            return midpoint
        else:
            if target < aList[midpoint]:
                return recursiveBinarySearch(aList, target, start, midpoint-1)
            else:
                return recursiveBinarySearch(aList ,target, midpoint+1, end)

print(recursiveBinarySearch(aList,455, 0, len(aList)))