当 bisect_left 和 bisect_right 不相等时是什么情况？

Question

据我的理解，bisect_left和bisect_right是进行二分查找的两种不同方式：一种从左边开始，另一种从右边开始。因此，它们的结果应该是相同的。在什么情况下这两者会不相等呢？即假设要搜索的列表和值相同的情况下，它们何时会返回不同的结果？

- user1691278

Answer 1

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

另一个问题是何时它们等效？回答这个问题后，你的问题的答案就清晰了。

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

- Steve P.

Answer 2

当要查找的目标在列表中时，bisect_left和bisect_right会返回不同的结果。

例如：

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

- falsetru

Answer 3

bisect_left 和 bisect_right 在查找元素存在于列表中时会返回不同的结果。

实际上，bisect_left 更加实用，因为如果所查找的元素在列表中存在，它将返回该元素的索引。

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

使用 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并得到相同的结果，上面的代码将有一个小变化。

- Pranjal Mittal

---

二分查找使用bisect实现的有趣点！ - information_interchange

Answer 4

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

• bisect_left 返回最大的索引，以便插入元素相对于<
• bisect_right 返回最大的索引，以便插入元素相对于<=

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

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

这种行为可以简化为：

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

- bluenote10

---

我喜欢这个概念上的答案，但仍然不够清晰。bisect_left返回索引0，因为这是插入元素真正较小的最大可能插入索引。比什么更小？在示例中出现的唯一数字是0（因此问题中没有任何数字比其他数字更小）。填写这一点会有所帮助！谢谢！ - Dan Nissenbaum

@DanNissenbaum 给定列表中比给定数字小的数。如果有帮助的话，可以想象现有的列表是 [-1, -1, -1, 0, 0, 0, 1, 1, 1]。现在，如果你对 -1、0 或 1 中的任何一个进行二分查找，"left" 变体将给出相应元素在现有列表中最左边的索引，而 "right" 变体将给出相应元素在现有列表中最右边的索引。如果你对 -2、0.5 或 2 等值进行二分查找，则两个变体返回相同的索引，即它们只在“搜索的”元素等于某个现有元素的情况下不同。 - bluenote10

你能具体说明一下"w.r.t"是什么意思吗？ - Chubi Best

@ChubiBest 是的，我现在已经明确了。大致是指“关于”/“有关”/“就...而言”。 - bluenote10

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_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`使用`<`，将搜索窗口移动到值的左侧（如果其存在）。否则（如果该值不存在于数组中），两种实现将产生相同的输出结果。

- Hossein Mousavi

Answer 6

需要了解两件事情： bisect.bisect 和 bisect.bisect_right 的工作方式相同。它们返回元素可以插入而不破坏元素顺序的最右侧位置。但与上面相反，bisect.bisect_left 返回元素可以插入的最左侧位置。请谨慎使用。

- user5449023