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

Question

所以我写了一个二进制搜索算法，但是当我测试运行时它并不能完美地工作。

这是代码

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

abd这里是调用函​​数的代码

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)

问题是这样的，当我实际运行它给出的函数时，我想将列表 target_values 添加到第一个正确的顺序中

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]

Answer 1

只需将函数更改为返回 (-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 是插入索引，但它永远不会超出循环中的当前列表，因为当值被插入到列表末尾时它应该.