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
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.
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
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.
-
3Interesting point about binary search being implemented with bisect! Oct 22, 2019 at 17:26
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.
-
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 are0
(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
, or1
, 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
, or2
, both variants return the same index, i.e., they only differ in cases where the "searched for" element is equal to some existing element. May 22, 2022 at 6:23 -
-
@ChubiBest Yes, I've spelled it out now. Something along "with reference to" / "with regards to" / "with respect to". Jun 17 at 6:42
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.
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.