python - 二进制搜索算法不起作用

所以我写了一个二进制搜索算法，但当我做测试运行时，它并不完美。
这是密码

def binarySearch(lst, target):
    low = 0
    high = len(lst)-1
    while high >= low:
        mid = (high + low)//2
        if target < lst[mid]:
           high = mid - 1
        elif target > lst[mid]:
            low = mid + 1
        else:
            return mid

    return (-1 * (mid+1))

这里是调用函数的代码

lst_test = [3, 4, 6, 7]
target_values = [1, 3, 5, 8]

for t in target_values:
    i = binarySearch(lst_test, t)
    if (i < 0):
        print("In", lst_test, t, "is going to be inserted at index",-1*(i+1))
        lst_test.insert((i+1)*-1, t)
    else:
        print("In", lst_test, t, "was found at index", i)
print("The final list is:", lst_test)

问题是，当我实际运行它给出的函数时，我想将list target_值添加到lst的正确顺序中

In [3, 4, 6, 7] 1 is going to be inserted at index 0
In [1, 3, 4, 6, 7] 3 was found at index 1
In [1, 3, 4, 6, 7] 5 is going to be inserted at index 3
In [1, 3, 4, 5, 6, 7] 8 is going to be inserted at index 5
The final list is: [1, 3, 4, 5, 6, 8, 7]

这很奇怪，它的工作，但它只在调用的最后一部分失败
有什么办法解决这个问题吗最终清单应为[1,3,4,5,6,7,8]
按要求我跟踪了我的二进制搜索算法，它的安静质量差我希望这会有帮助

Mid point is:  1
target value is smaller than a mid point
Mid point is:  0
target value is smaller than a mid point
In [3, 4, 6, 7] 1 is going to be inserted at index 0
Mid point is:  2
target value is smaller than a mid point
Mid point is:  0
target value is larger than a mid point
Mid point is:  1
Found the index location at  1
In [1, 3, 4, 6, 7] 3 was found at index 1
Mid point is:  2
target value is larger than a mid point
Mid point is:  3
target value is smaller than a mid point
In [1, 3, 4, 6, 7] 5 is going to be inserted at index 3
Mid point is:  2
target value is larger than a mid point
Mid point is:  4
target value is larger than a mid point
Mid point is:  5
target value is larger than a mid point
In [1, 3, 4, 5, 6, 7] 8 is going to be inserted at index 5
The final list is: [1, 3, 4, 5, 6, 8, 7]

最佳答案

只需将函数改为返回(-1 * (low+1))：

def binarySearch(lst, target):
    low = 0
    high = len(lst)-1
    while high >= low:
        mid = (high + low)//2
        if target < lst[mid]:
           high = mid - 1
        elif target > lst[mid]:
           low = mid + 1
        else:
           return mid

    return (-1 * (low+1))

输出：

('In', [3, 4, 6, 7], 1, 'is going to be inserted at index', 0)
('In', [1, 3, 4, 6, 7], 3, 'was found at index', 1)
('In', [1, 3, 4, 6, 7], 5, 'is going to be inserted at index', 3)
('In', [1, 3, 4, 5, 6, 7], 8, 'is going to be inserted at index', 6)
('The final list is:', [1, 3, 4, 5, 6, 7, 8])

原始实现的问题是，代码假定mid是插入索引，但它永远不能超出循环中的当前列表，因为当值插入到列表的末尾时，它应该是这样的。