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

仅分解出二等分函数，并将其与“检测重复”代码分开进行测试，“检测重复”代码是一个单独的算法。

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

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