W moim zrozumieniu Bisect_left i Bisect_right to dwa różne sposoby robienia tego samego: rozcięcia, pochodzi z lewej i drugiej pochodzących z prawej strony. Tak więc wynika, że mają ten sam wynik. W jakich okolicznościach są te dwa nie są równe, tj. Kiedy zwracają różne wyniki, zakładając listę, a wartość przeszukiwana jest taka sama?

29
user1691278 30 listopad 2013, 10:18

5 odpowiedzi

Najlepsza odpowiedź

bisect.bisect_left Zwraca największą liczbę miejsca na posortowanej lista, aby wstawić dany element. bisect.bisect_right Zwraca w prawo w odpowiedniej lista, aby wstawić dany element.

Alternatywne pytanie brzmi, gdy są równoważne? Odpowiadając na to odpowiedź na twoje pytanie staje się jasne.

Są równoważne, gdy element do wstawiania nie jest obecny na liście. Dlatego nie są one równoważne, gdy element do wstawiania znajduje się na liście.

50
Steve P. 30 listopad 2013, 06:21

Ponieważ inni wskazali, bisect_left i bisect_right zwracają różne wyniki, gdy podejrzany element jest obecny na liście.

Okazuje się, że bisect_left jest bardziej przydatny pod ręką, ponieważ zwraca dokładny indeks elementu, który spojrzał w górę, jeśli jest obecny na liście.

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

Przykład binary_search , który używa 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

W powyższym kodzie pojawi się niewielka zmiana, jeśli chcesz użyć bisect_right zamiast bisect_left i uzyskać ten sam wynik.

10
Pranjal Mittal 3 grudzień 2013, 09:08

Dla mnie ta interpretacja bisect_left / bisect_right sprawia, że jest bardziej jasny:

  • bisect_left Zwraca największy indeks wstawienia elementu w.r.t. <
  • bisect_right Zwraca największy indeks wstawienia elementu w.r.t. <=

Na przykład, jeśli dane są [0, 0, 0] i zapytasz o 0:

  • bisect_left Zwraca indeks 0, ponieważ jest to największy możliwy indeks wkładki, w którym wstawiony element jest naprawdę mniejszy.
  • bisect_right Zwraca indeks 3, ponieważ z "mniejszym lub równym" postępy wyszukiwania poprzez identyczne elementy.

To zachowanie może być uproszczone do:

  • bisect_left Wstawiałby elementy po lewej stronie identycznych elementów.
  • bisect_right Wkłada elementy do prawa identycznych elementów.
6
bluenote10 7 czerwiec 2019, 11:01

Istnieją dwie rzeczy, które należy rozumieć: bisect.bisect i bisect.bisect_right działa w ten sam sposób. Powracają te pozycję w prawo, w której można włożyć element bez łamania kolejności elementów. Ale w przeciwieństwie do powyższego, bisect.bisect_left zwraca największą pozycję, w której można włożyć element. Używaj ostrożnie.

4
AndreyS Scherbakov 27 styczeń 2020, 02:08

Gdy cel do lokalizacji znajduje się na liście, bisect_left, bisect_right zwraca inny wynik.

Na przykład:

>>> import bisect
>>> bisect.bisect_left([1,2,3], 2)
1
>>> bisect.bisect_right([1,2,3], 2)
2
27
falsetru 30 listopad 2013, 06:18