Python 中的二进制搜索超出时间限制

Question

我已经在 python 中创建了一个二分查找程序，但其中一个测试用例出现“超出时间限制”的情况。知道如何优化我的代码以减少运行时间吗？

我的代码基本上找到了中位数项的索引，并将查询与中位数的整数进行比较。然后我将数组更新为左半部分（如果查询小于中位数）或右半部分（如果查询大于中位数）。

如果查询等于中位数，则返回索引。

如果数组长度为1，且查询不等于数组中的唯一整数，则返回-1。否则返回数组中唯一整数的索引。

下面是我的代码。

感谢大家的帮助！

def binary_search(keys, query):
    array_to_search = keys
    
    while len(array_to_search) > 1:
        median = len(array_to_search) // 2
        if q < array_to_search[median]:
            # split list from starting point up to median index
            array_to_search = array_to_search[:median]
            continue
        elif q > array_to_search[median]:
            # split list from median index up to last index
            array_to_search = array_to_search[median:]
            continue
        else:
            return keys.index(array_to_search[median])
    
    if q == array_to_search[0]:
        return keys.index(array_to_search[0])
    else:
        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=' ')

Answer 1

您的算法处于无限循环中，因此出现“超出时间限制”错误。

需要注意的是，肯定有更有效的方法来实现二分查找，我认为可以调整您的逻辑以制作一个工作版本，如下所示：

#def binary_search(keys, query): # used different argument name 'query' from the name 'q' used in the function body
def binary_search(keys, q):
    array_to_search = keys
    
    i = 0 # we need to track changes to the start of the array
    while len(array_to_search) > 1:
        median = len(array_to_search) // 2
        if q < array_to_search[median]:
            # split list from starting point up to median index
            array_to_search = array_to_search[:median]
            continue
        elif q > array_to_search[median]:
            # split list from median index up to last index
            #array_to_search = array_to_search[median:] # median has already been checked, so we can start at median + 1 instead
            array_to_search = array_to_search[median + 1:]
            i += median + 1 # we need to track changes to the start of the array
            continue
        else:
            return i + median # return value needs to reflect changes to the start of the array
    
    #if q == array_to_search[0]: # we need to check that the array is not empty
    if array_to_search and q == array_to_search[0]:
        return i # return value needs to reflect changes to the start of the array
    else:
        return -1

def foo():
    '''
    #I have eliminated the input logic for testing purposes
    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
    '''

    # here is an arbitrary test case
    input_keys = [0,2,4,6,8,10,12,14,16,18,20]
    input_queries = [0,6,12,18,20,-1,9,21]

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

foo()

输出：

0 3 6 9 10 -1 -1 -1

关于效率改进，请注意 array_to_search[:median] 和 array_to_search[median + 1:] 等切片操作将制作副本，第一个需要 n/2 时间，然后 n/4 第二个，然后是 n/8 等，将 O(n) 时间复杂度添加到二进制搜索中，否则该算法可能是 O(log n)。这就是为什么通常使用两个指针（例如 left 和 right）来跟踪执行搜索的 ever-shrinking 子数组的原因。您可能想看看 Wikipedia 中的示例。

Python 中的二进制搜索超出时间限制

Time Limit Exceeded for Binary Search in Python

python

algorithm

search

binary-search