0Pricing
Coding Interview Prep · Lekcja

bisect_left i bisect_right

Znajdowanie miejsc wstawienia w posortowanej liście

bisect_left i bisect_right to bezpłatna lekcja Coding Interview Prep 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep 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 bisect

Miejsca 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)  # 1

bisect_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)  # 4

Policz 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)  # 3

Czy 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] == x

Pierwszy 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 >= x

Pierwszy 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 > x

Wstaw 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 sorted

Przeszukuj 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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „bisect_left i bisect_right”?

Znajdowanie miejsc wstawienia w posortowanej liście Ćwiczysz Coding Interview Prep 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ąć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep 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 Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep 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

  1. Klasyczne wyszukiwanie binarne bez błędów
  2. bisect_left i bisect_right
  3. Pierwsza wartość True: wyszukiwanie binarne predykatu
  4. Wyszukiwanie binarne po odpowiedzi
← Powrót do Coding Interview Prep