bisect_left i bisect_right
Znajdowanie miejsc wstawienia w posortowanej liście
bisect_left i bisect_right to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Wyszukiwanie bez kodu pomocniczego
Moduł bisect języka Python udostępnia przetestowane wyszukiwanie binarne dla posortowanych list. Brak ręcznie napisanej pętli oznacza brak błędów pominięcia o jeden do debugowania.
import bisectMiejsca wstawienia, nie wartości logiczne
Zamiast wartości true lub false moduł bisect zwraca indeks, pod którym można wstawić wartość, zachowując sortowanie listy. To właśnie ten indeks jest najważniejszą zaletą.
a = [1, 3, 3, 3, 7]bisect_left wybiera lewą stronę
bisect_left zwraca pierwszą pozycję, na której można umieścić daną wartość. W przypadku duplikatów wskazuje miejsce przed wszystkimi równymi elementami, nigdy za nimi.
bisect.bisect_left(a, 3) # 1bisect_right wybiera prawą stronę
bisect_right zwraca pozycję tuż za ostatnim równym elementem. W przypadku duplikatów wskazuje miejsce za wszystkimi pasującymi wartościami.
bisect.bisect_right(a, 3) # 4Policz równe elementy
Odejmij te dwie wartości, aby w czasie O(log n) policzyć duplikaty danej wartości. right minus left daje dokładnie liczbę jej wystąpień.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3Czy wartość występowała?
Aby sprawdzić przynależność, pobierz i z bisect_left i potwierdź, że a[i] równa się celowi. Najpierw sprawdź, czy i nie osiągnęło długości listy.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xPierwszy element co najmniej równy X
bisect_left znajduje również pierwszy element większy lub równy x. Ten indeks wskazuje bezpośrednio odpowiedź dla dolnego ograniczenia.
i = bisect.bisect_left(a, x) # first >= xPierwszy element ściśle większy
Potrzebujesz pierwszego elementu ściśle większego od x? bisect_right zwraca ten indeks bezpośrednio — jest odpowiednikiem górnego ograniczenia.
i = bisect.bisect_right(a, x) # first > xWstaw i zachowaj sortowanie
insort znajduje właściwe miejsce i wstawia element w jednym wywołaniu, zachowując uporządkowanie listy. Jest to przydatne podczas budowania posortowanej struktury w locie.
bisect.insort(a, 5) # a stays sortedPrzeszukuj wybrany zakres
Opcjonalne argumenty lo i hi ograniczają wyszukiwanie do wycinka. Dzięki temu nie trzeba tworzyć kopii, gdy interesuje Cię tylko podzakres.
bisect.bisect_left(a, x, 2, 5)Klucze za pomocą pomocniczej listy
bisect porównuje całe elementy, więc aby wyszukiwać według pola, utwórz równoległą listę zawierającą tylko te klucze i użyj bisect właśnie na niej.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Szybkie sprawdzenie
Przeanalizuj duplikaty i miejsca wstawienia.
Podsumowanie: biegłość w bisect
Potrafisz już znajdować miejsca wstawienia, liczyć duplikaty oraz znajdować dolne i górne ograniczenia w czasie logarytmicznym. Zanim napiszesz pętlę, sięgnij po bisect. ✨
Często zadawane pytania
Czy lekcja „bisect_left i bisect_right” jest bezpłatna?
Tak — pełny tekst „bisect_left i bisect_right” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „bisect_left i bisect_right”?
Znajdowanie miejsc wstawienia w posortowanej liście Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „bisect_left i bisect_right”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Klasyczne wyszukiwanie binarne bez błędów
- bisect_left i bisect_right
- Pierwsza wartość True: wyszukiwanie binarne predykatu
- Wyszukiwanie binarne po odpowiedzi