python - 使用二进制搜索返回下一个最高值

Question

在我的二进制搜索中，如果找不到目标，我想返回下一个最高元素的索引。

例如 [1,2,3,4,5,7]如果我要搜索 6它应该返回 7 的位置.

我正在测试 aList = [2, 8, 17, 42, 79, 85]

当我搜索 3 时它起作用了, 18 , 或 80 .但是，当我搜索 9 时，它返回的索引比应有的索引低 1。 , 43 , 或 86 .

def recursiveBinarySearch(aList, first, last, target):

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

Answer 1

aList = [1,3,5,6,8,9,10,12,34,56,78,456, 777]
def recursiveBinarySearch(aList, target, index):
    #aList = sorted(aList)
    print(aList, index)
    if len(aList) <= 1:
        if index==0 and aList[0]==target:
            return index
        else:   
            return index+1

    else:
        midpoint = len(aList) // 2
#        print(midpoint)
        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,3,0))

这应该有效:) 修复了搜索第一个数字时的错误。