Python

Question

我一直在研究二分查找问题。

问题要求我将键列表（列表 B）与另一个列表（列表 A）匹配，而不是将一个键编号与给定列表匹配。如果键与列表 A 中的数字匹配，则输出应 return A 中存在该数字的第一个索引。如果列表 A 中不存在密钥编号，则 return -1

假设列表 A 和列表 B 是：

A = [1, 5, 8, 12, 13]
B = [8, 1, 23, 1, 11]

由于两个列表中都存在 8，因此输出为 2，因为列表 A 中的 8 在 [2] 中。使用这个逻辑，最终的整体输出应该变成：

matched_list = [2, 0, -1, 0, -1]

下面是我的代码。如果您也能在行内找到任何逻辑错误，我们将不胜感激，但是，我最担心的是运行时间。当我在我的电脑上按回车键时，处理了很长时间，软件（我使用的是 VS Code）最终崩溃了。

我有 16GB RAM 和 Intel Core i7，所以拖累它的不应该是设备，而是算法。

def binary_search(A, B, n):
# We match the numbers in key list, B, to the numbers in A

    low, high = 0, n-1
    # low limit is initialised to A[0], the first number of list A
    # high limit initialised to the last number of the list, A[n-1]

    matched_list = []

    for i in B:
        middle = (high+low)//2

        while low <= high:
            if i > A[middle]:
                low = middle+1 

            elif i < A[middle]:
                high = middle-1 
            
            else:
                matched_list.append(middle)
    
        if low > high:
            return(-1)

    return(matched_list)

A = [1, 5, 8, 12, 13]
B = [8, 1, 23, 1, 11]
n = 5  # this is the length of list A


print(binary_search(A, B, n))

有没有办法改进我的算法？

Answer 1

我修复了函数中的错误。看到这段代码：

def binary_search(A, B, n):
    matched_list = []

    for i in B:
        low, high = 0, n - 1
        while low <= high:
            middle = (high + low) // 2
            if i > A[middle]:
                low = middle + 1
            elif i < A[middle]:
                high = middle - 1
            else:
                matched_list.append(middle)
                break

        if low > high:
            matched_list.append(-1)

    return matched_list

Answer 2

在您的代码中，

while low <= high:
            if i > A[middle]:
                low = middle+1 

            elif i < A[middle]:
                high = middle-1 
            
            else:
                matched_list.append(middle)

else 语句没有中断，因此它陷入了无限循环。添加 break 语句即可解决。
建议：由于 maps/dictionaries 往往更快，您可以在 O(N) 而不是 O(NlogN).

中使用它们来有效解决此问题

Answer 3

1st - 如果 space 未排序，则不能使用二进制搜索。

2nd - 如果你想要更好的算法使用地图，复杂度将是线性的

3rd - 如果你想使用二进制搜索，你可以很容易地在集合中插入你的值，然后用 lower_bound.[=10= 找到答案]

Answer 4

@cliff_leaf，在您的情况下，仅使用 dict() 将数字索引保存在字典中以便 B 稍后进行快速 O(1) 查找会更容易：（二进制搜索可能在这种情况下不合适。）您可以在找到第一个匹配数字时将代码调整为 break/exit - 8 并停止，如果这是您想要的 - 找到第一个匹配。

>>> A = [1, 5, 8, 12, 13]
>>> B = [8, 1, 23, 1, 11]
>>> aa = {n: i for i, n in enumerate(A)}
>>> aa
{1: 0, 5: 1, 8: 2, 12: 3, 13: 4}
>>> for n in B:
    if n in aa: print(aa[n])

    
2
0
0

Python - 二分查找速度太慢导致计算机崩溃 - 我该如何改进算法

Python - Binary search being too slow and crashes computer - how can I improve the algorithm

algorithm

binary-search