python - 如何返回 Python 数组中目标元素的索引？

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)))