When are bisect_left and bisect_right not equal?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

As the others have pointed out, 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 at hand, since it returns the exact 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.