二分查找陷入无限循环 python

Question

我的二进制搜索似乎陷入了无限循环，因为它没有为我的测试数据输出任何内容。 second_list 已排序，我正在检查第一个列表中的重复项，然后将这些重复项添加到空列表中。我的二进制搜索算法一直执行到剩下一个元素，然后我检查它是否与项目相同，我想保留这个结构。我认为问题是右指针没有减少，但我不明白为什么会这样。

def detect_duplicates_binary(first_list, second_list):

    duplicates_list = []

    for item in first_list:

        left = 0
        right = len(second_list) - 1

        while left < right:

            midpoint = (left + right) // 2

            if second_list[midpoint] > item:
                right = midpoint - 1
            else:
                left = midpoint

        if (second_list[left] == item):
            duplicates_list.append(item)

    return duplicates_list

Answer 1

病理学

这是一个可能导致无限循环的执行顺序：

>>> left = 10
>>> right = 11
>>> left < right
True
>>> midpoint = (left + right) // 2
>>> midpoint
10
>>> left = midpoint
>>> left
10
>>> # No change!

建议 1

只分解出对分函数，并从 "detect duplicates" 代码中单独测试它，这是一个单独的算法。

建议 2

使用 Python 自己的 bisect 模块 -- 它已经过测试和记录。

这是其代码的简化版本：

def bisect_right(a, x):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    """
    lo = 0
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

建议 3

右索引增加1:

right = len(second_list)

希望这对您有所帮助。祝你好运:-)

二分查找陷入无限循环 python

Binary search stuck in an infinte loop python

python

binary-search

病理学

建议 1

建议 2

建议 3