Klasyczne wyszukiwanie binarne bez błędów
Poprawne zaplanowanie pętli low, high i mid
Klasyczne wyszukiwanie binarne bez błędów to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 1 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.
Zmniejsz przestrzeń wyszukiwania o połowę
Wyszukiwanie binarne znajduje wartość na posortowanej liście, zmniejszając zakres o połowę w każdym kroku. Dzięki temu powolne przeszukiwanie O(n) zmienia się w szybkie wyszukiwanie O(log n).
a = [1, 3, 5, 7, 9] # must be sortedSortowanie to jedyna zasada
Wyszukiwanie binarne działa tylko na posortowanych danych. Jeśli lista jest nieuporządkowana, należy najpierw ją posortować, ponieważ w przeciwnym razie wynik będzie pozbawiony znaczenia i błędny.
a.sort() # ascending order requiredDwie granice
Zacznij od dwóch wskaźników: low na indeksie 0 oraz high na ostatnim indeksie. Jeśli cel znajduje się w tablicy, zawsze leży między nimi.
low, high = 0, len(a) - 1Bezpiecznie znajdź środek
Oblicz mid jako low + (high - low) // 2. W Pythonie przepełnienie nie stanowi problemu, ale ta postać jest bezpiecznym nawykiem niezależnie od języka.
mid = low + (high - low) // 2Trzy możliwości
Porównaj a[mid] z celem. Albo znajdziesz wartość, albo będzie ona za mała, albo za duża. Każdy przypadek zmniejsza zakres w inny sposób.
if a[mid] == target:
return midZa mała — idź w prawo
Jeśli a[mid] jest mniejsze od celu, odpowiedź musi znajdować się po prawej stronie. Przesuń low na mid + 1 i odrzuć lewą połowę.
elif a[mid] < target:
low = mid + 1Za duża — idź w lewo
Jeśli a[mid] jest większe od celu, przeszukaj lewą połowę. Przesuń high na mid - 1, aby nie sprawdzać ponownie mid.
else:
high = mid - 1Warunek pętli
Kontynuuj while low is less than or equal to high. Gdy wskaźniki się miną, zakres jest pusty, a celu nie ma w tablicy.
while low <= high:
mid = low + (high - low) // 2Zgłoś brak wyniku
Jeśli pętla zakończy się bez znalezienia dopasowania, wartość nie występuje w tablicy. Zgodnie z konwencją zwróć -1, aby wywołujący mógł odróżnić sukces od niepowodzenia.
return -1 # target not in listPułapka pominięcia o jeden
Klasyczny błąd polega na pominięciu +1 lub -1 podczas przesuwania wskaźnika. Wtedy mid jest sprawdzane w nieskończoność, co prowadzi do nieskończonej pętli.
low = mid + 1 # not low = midKorzystaj z biblioteki, gdy to możliwe
W przypadku zwykłego sprawdzania przynależności moduł bisect języka Python zawiera już wyszukiwanie wolne od błędów. Własną pętlę należy pisać tylko wtedy, gdy potrzebna jest niestandardowa logika.
import bisect
i = bisect.bisect_left(a, target)Szybkie sprawdzenie
Zastanów się, co sprawia, że pętla działa poprawnie.
Podsumowanie: wyszukiwanie bez błędów
Potrafisz już ustawić low i high, bezpiecznie obliczyć mid, zmniejszać właściwą część zakresu i unikać pułapki pominięcia o jeden. Wyszukiwanie logarytmiczne jest już w Twoim repertuarze. 🎯
Często zadawane pytania
Czy lekcja „Klasyczne wyszukiwanie binarne bez błędów” jest bezpłatna?
Tak — pełny tekst „Klasyczne wyszukiwanie binarne bez błędów” 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 „Klasyczne wyszukiwanie binarne bez błędów”?
Poprawne zaplanowanie pętli low, high i mid Ć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 1 z 4.
Ile czasu zajmuje lekcja „Klasyczne wyszukiwanie binarne bez błędów”?
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