Когда bisect_left и bisect_right не равны?

В моем понимании, bisect_left и bisect_right - это два разных способа сделать одно и то же: bisection, один из которых идет слева, а другой - справа. Отсюда следует, что они имеют одинаковый результат. При каких обстоятельствах эти два не равны, т.е. Когда они возвратят разные результаты, если предположить, что список и значение, которое выполняется поиск, одинаковы?

Ответы

Ответ 1

bisect.bisect_left возвращает самое левое место в отсортированном списке, чтобы вставить данный элемент. bisect.bisect_right возвращает самое правое место в отсортированном списке, чтобы вставить данный элемент.

Альтернативный вопрос: когда они эквивалентны? Отвечая на этот вопрос, ответ на ваш вопрос становится ясным.

Они эквивалентны, когда элемент, который нужно вставить, отсутствует в списке. Следовательно, они не эквивалентны, когда элемент, который нужно вставить, находится в списке.

Ответ 2

Когда целевой объект находится в списке, bisect_left, bisect_right возвращают другой результат.

Например:

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

Ответ 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 и получить тот же результат.

Ответ 4

Есть две вещи, которые следует понимать: bisect.bisect и bisect.bisect_right работают одинаково. Они возвращают крайнее правое положение, где элемент может быть вставлен. Но в отличие от выше, bisect.bisect_left возвращает крайнее левое положение, где элемент может быть вставлен. Используйте осторожно.

Ответ 5

Для меня эта интерпретация bisect_left/bisect_right делает это более ясным:

  • bisect_left возвращает самый большой индекс для вставки элемента wrt <
  • bisect_right возвращает самый большой индекс для вставки элемента wrt <=

Например, если ваши данные [0, 0, 0] и вы запрашиваете 0:

  • bisect_left возвращает индекс 0, потому что это максимально возможный индекс вставки, где вставленный элемент действительно меньше.
  • bisect_right возвращает индекс 3, потому что при "меньшем или равном" поиск продвигается через идентичные элементы.