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

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

尝试编辑接受的答案，因为在搜索高于列表中的数字时失败，但由于某些原因，操作人员不接受编辑，这意味着答案仍然是错误的。既然如此，我就把答案贴在这里。这个答案不仅修复了当被要求查找一个大于不在列表中的值时的IndexError，而且还将参数更改为kwargs，这样我们就不必每次调用函数时都传入它们

aList = [-1,1,3,5,6,8,9,10,12,34,56,78,456] 

def binary_search(arr,item,low = 0, high = None):
    if high == None:
        high = len(arr)
    mid = low + (high-low) //2  
    if high - low + 1 <= 0 or mid==high:
        return False
    else:
        guess = arr[mid]
        if guess == item:
            return mid
        if item < guess:
            return binary_search(arr, item, low, mid)
        else:
            return binary_search(arr, item, (mid+1), high)

(binary_search(aList,457))

Answer 2

你的算法给出了最后一个拆分列表中的索引。 因此，对于您的答案，如果您打印9的列表，我们将得到以下信息：

[1, 3, 5, 6, 8, 9, 10, 12, 34, 56, 78, 456]
[1, 3, 5, 6, 8, 9]
[8, 9]

Wich返回索引1。这对于最后一个列表[8, 9]是正确的。 通过重新计算列表的长度，可以很容易地解决这个问题。

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

    if len(aList) == 0:
        return False
    else:
        midpoint = len(aList) // 2

        if aList[midpoint] == target:
            return aList.index(target)+index
        else:
            if target < aList[midpoint]:
                return recursiveBinarySearch(aList[:midpoint],target, index)
            else:
                return recursiveBinarySearch(aList[midpoint:],target, index+len(aList[:midpoint]))


print(recursiveBinarySearch(aList,56,0))

这比以前的解决方案占用的内存少一点。当然，这也更快，虽然这是边缘。

Answer 3

这是因为每次进行递归调用时，都会传递一个不同的修改列表，并且每个调用中的索引都会更改。例如，如果在数组的后半部分搜索一个数字，则最终返回的值将小于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)))