bisect_left和bisect_right何时不相等？

Question

在我的理解中,bisect_left和bisect_right是做同样事情的两种不同方式:二分法,一个来自左边,另一个来自右边.因此,它们具有相同的结果.假设列表和正在搜索的值是相同的,在什么情况下这两者不相等,即它们什么时候会返回不同的结果？

Answer 1

bisect.bisect_left返回排序列表中最左边的位置以插入给定元素. bisect.bisect_right返回排序列表中最右边的位置以插入给定元素.

另一个问题是它们何时相同？通过回答这个问题,你的问题的答案就变得清晰了.

当要插入的元素不在列表中时,它们是等效的.因此,当要插入的元素在列表中时,它们不等效.

Answer 2

当要定位的目标位于列表中时bisect_left,bisect_right返回不同的结果.

例如:

>>> import bisect
>>> bisect.bisect_left([1,2,3], 2)
1
>>> bisect.bisect_right([1,2,3], 2)
2

Answer 3

正如其他人所指出的那样,当被查找的元素出现在列表中时,bisect_left和bisect_right返回不同的结果.

事实证明,bisect_left在手头更有用,因为它返回了列表中存在的元素的确切索引.

>>> import bisect
>>> bisect.bisect_left([1,2,3,4,5], 2)
1

的实施例binary_search使用bisect_left:

from bisect import bisect_left

def binsearch(l,e):
    '''
    Looks up element e in a sorted list l and returns False if not found.
    '''
    index = bisect_left(l,e)
    if index ==len(l) or l[index] != e:
        return False
    return index

如果你想使用bisect_right而不是bisect_left并获得相同的结果,上面的代码会有一个小的变化.

Answer 4

对我来说，对bisect_left/ 的这种解释bisect_right更清楚：

• bisect_left 返回插入元素的最大索引wrt <
• bisect_right 返回插入元素的最大索引wrt <=

例如，如果您的数据是[0, 0, 0]并且您查询0：

• bisect_left 返回索引 0，因为这是插入元素真正较小的最大可能插入索引。
• bisect_right 返回索引 3，因为使用“更小或等于”搜索会在相同的元素中前进。

这种行为可以简化为：

• bisect_left 将在相同元素的左侧插入元素。
• bisect_right 将在相同元素的右侧插入元素。

Answer 5

bisect_left并bisect_right返回最左边和最右边的索引，可以在不改变元素顺序的情况下插入该值。如果列表中不存在该值，则它们都返回相同的索引。当值存在于列表中时就会出现差异。例如，要在不破坏顺序的情况下插入10列表[10,20,30]，最左边的索引将为0，最右边的索引将为1。但是，要插入10.5到同一列表中，最左边和最右边的索引都将等于1。这是代码中的相同示例：

>>> from bisect import bisect_left, bisect_right
>>> bisect_left([10,20,30],10)
<<< 0
>>> bisect_right([10,20,30],10)
>>> 1

，对于该值存在于数组中的情况，并且

>>> bisect_left([10,20,30],10.5)
<<< 1
>>> bisect_right([10,20,30],10.5)
>>> 1

，用于数组中不存在该值的情况。

通过查看它们的实现，可以清楚地看出bisect_left和之间的区别。bisect_right下面是显示其准系统实现的代码片段（取自 python 标准库）：

def bisect_right(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] <= x:    # <--- less than or equal to
            lo = mid+1
        else:
            hi = mid
    return lo


def bisect_left(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:    # <--- less than
            lo = mid + 1
        else:
            hi = mid
    return lo

两者之间的唯一区别在于将中点值与查找值进行比较的条件。bisect_right使用<=，意味着如果数组中存在该值，它将把搜索窗口移动到元素的右侧，而使用bisect_left，<将搜索窗口移动到该值的左侧（如果存在）。否则（如果数组中不存在该值），这两种实现会产生相同的输出。

Answer 6

有两件事需要理解： bisect.bisect并且bisect.bisect_right以同样的方式工作。它们返回可以在不破坏元素顺序的情况下插入元素的最右边位置。但与上面相反，bisect.bisect_left返回可以插入元素的最左边位置。小心使用。