二进制搜索输出给出错误答案

Question

这是我的代码：

def binary_search(keys, query):
    low, high = 0, 0
    while low <= high:
        midpoint = low + (high - low) // 2
        if query == keys[midpoint]:
            return midpoint
        elif keys[midpoint] > query:
            high = midpoint - 1 
        else:
            low = midpoint + 1
    return -1       
           

if __name__ == '__main__':
    num_keys = int(input())
    input_keys = list(map(int, input().split()))
    assert len(input_keys) == num_keys

    num_queries = int(input())
    input_queries = list(map(int, input().split()))
    assert len(input_queries) == num_queries

    for q in input_queries:
        print(binary_search(input_keys, q), end=' ')

我正在输入：

5
1 5 8 12 13
5
8 1 23 1 11

我应该得到这个作为输出：

2 0 -1 0 -1

但我得到的是这个：

-1 0 -1 0 -1

Answer 1

想一想当您在 1 5 8 12 13 中寻找 8 时会发生什么。

low 和 high 开始时分别是 0 和 0。 midpoint 因此是 0.

keys[midpoint] 是 1.

这小于query，也就是8。因此 low 被设置为 1。 low 现在大于 high 所以循环结束，函数 returns -1.

Answer 2

您开始时 low 和 high 都等于 0，这没有意义。将前两行更改为以下内容：

low, high = 0, len(keys)
while low < high:

二进制搜索输出给出错误答案

Binary Search Output giving wrong answer

python

binary-search

python-3.x