59

In my understanding, bisect_left and bisect_right are two different ways of doing the same thing: bisection, one coming from the left and the other coming from the right. Thus, it follows that they have the same result. Under what circumstances are these two not equal, i.e. when will they return different results, assuming the list and the value that is being searched are the same?

6 Answers 6

107

bisect.bisect_left returns the leftmost place in the sorted list to insert the given element. bisect.bisect_right returns the rightmost place in the sorted list to insert the given element.

An alternative question is when are they equivalent? By answering this, the answer to your question becomes clear.

They are equivalent when the the element to be inserted is not present in the list. Hence, they are not equivalent when the element to be inserted is in the list.

48

When the target to locate is in the list, bisect_left, bisect_right return different result.

For example:

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

bisect_left and bisect_right return different results when the element being looked up is present in the list.

It turns out that bisect_left is more useful in practice, since it returns the index of the element being looked up if it is present in the list

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

Example of binary_search that uses 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

There will be a small change in the above code, if you want to use bisect_right instead of bisect_left and get the same result.

1
  • 3
    Interesting point about binary search being implemented with bisect! Oct 22, 2019 at 17:26
17

To me this interpretation of bisect_left/bisect_right makes it more clear:

  • bisect_left returns the largest index to insert the element with respect to <
  • bisect_right returns the largest index to insert the element with respect to <=

For instance, if your data is [0, 0, 0] and you query for 0:

  • bisect_left returns index 0, because that's the largest possible insert index where the inserted element is truly smaller.
  • bisect_right returns index 3, because with "smaller or equal" the search advances through identical elements.

This behavior can be simplified to:

  • bisect_left would insert elements to the left of identical elements.
  • bisect_right would insert elements to the right of identical elements.
4
  • I love the answer conceptually, but it is nonetheless unclear. bisect_left returns index 0, because that's the largest possible insert index where the inserted element is truly smaller. Smaller than what? The only numbers that appear in the example are 0 (so no number in the problem is smaller than any other). It would help to fill that in! Thanks! Apr 24, 2022 at 16:34
  • 1
    @DanNissenbaum Smaller than the numbers in the given list. If it helps, imagine the existing list is [-1, -1, -1, 0, 0, 0, 1, 1, 1]. Now if you bisect for any of -1, 0, or 1, the "left" variant would give you the left-most index of the corresponding elements in the existing list, and the "right" variant would give you the right-most index. If you bisect for values like -2, 0.5, or 2, both variants return the same index, i.e., they only differ in cases where the "searched for" element is equal to some existing element.
    – bluenote10
    May 22, 2022 at 6:23
  • Could you specify what w.r.t means?
    – Chubi Best
    Jun 17 at 5:50
  • @ChubiBest Yes, I've spelled it out now. Something along "with reference to" / "with regards to" / "with respect to".
    – bluenote10
    Jun 17 at 6:42
7

bisect_left and bisect_right return the leftmost and rightmost index where the value can be inserted without changing the order of elements. If the value does not exist in the list, they both return the same index. The difference arises when the value exists in the list. For example, to insert 10 into the list [10,20,30] without breaking the order, the leftmost index would be 0, and the rightmost index would be 1. However, to insert 10.5 into the same list, both leftmost and rightmost indices would be equal to 1. Here is the same example in code:

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

, for the case when the value exists in the array, and

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

, for the case when the value does not exist in the array.

The difference between bisect_left and bisect_right becomes clear by looking at their implementation. Below is a code snippet showing their barebone implementation (taken from python standard library):

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

The only difference between the two is in the condition that compares the midpoint value with the lookup value. bisect_right uses <=, meaning that it will move the search window to the right of the element, if the value exists in the array, while bisect_left uses <, moving the search window to the left of the value (if it exists). Otherwise (if the value does not exist in the array), the two implementations result in the same output.

5

There are two things to be understood: bisect.bisect and bisect.bisect_right work the same way. These return the rightmost position where the element can be inserted without breaking the order of elements. But as opposed to the above, bisect.bisect_left returns the leftmost position where the element can be inserted. Use carefully.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.