Pierwsza wartość True: wyszukiwanie binarne predykatu
Wyszukiwanie monotonicznej granicy tak/nie
Pierwsza wartość True: wyszukiwanie binarne predykatu to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 3 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.
Znajdź granicę odpowiedzi tak/nie
W wielu problemach ukryty jest predykat monotoniczny: false, false, a potem już zawsze true. Wyszukiwanie binarne może znaleźć pierwszą wartość true bez posortowanej tablicy.
# FFFFTTTT -> find first TCo oznacza monotoniczność
Predykat jest monotoniczny, gdy po przyjęciu wartości true pozostaje true. To właśnie ta jedna własność pozwala wyszukać binarnie granicę.
def ok(x):
return x * x >= targetOkreśl przestrzeń odpowiedzi
Wybierz zakres, który na pewno zawiera granicę. Ustaw low na najmniejszą możliwą wartość, a high na wartość, dla której ok jest na pewno true.
low, high = 0, 10**9Sprawdź środek
Wyznacz mid i wywołaj ok(mid). Wynik logiczny mówi, którą połowę zachować — dokładnie tak jak porównanie wartości w zwykłym wyszukiwaniu binarnym.
mid = (low + high) // 2
if ok(mid):
...True oznacza, że można spróbować mniejszej wartości
Jeśli ok(mid) zwraca true, mid jest poprawną odpowiedzią, ale może działać również mniejsza wartość. Zachowaj mid, ustawiając high = mid, a nie mid - 1.
if ok(mid):
high = midFalse oznacza, że trzeba szukać wyżej
Jeśli ok(mid) zwraca false, granica leży powyżej mid. Odrzuć mid i wszystkie wartości poniżej, ustawiając low = mid + 1.
else:
low = mid + 1Wykonuj pętlę, dopóki low jest mniejsze od high
Użyj while low < high, a nie porównania mniejszości lub równości. Oba wskaźniki zbiegną się do pierwszego indeksu true, po czym pętla się zatrzyma.
while low < high:
mid = (low + high) // 2Odpowiedzią jest low
Po zakończeniu pętli low jest równe high i oba wskaźniki wskazują wartość pierwszą true. Zwróć low jako szukaną granicę.
return low # first x where ok(x)Dlaczego high = mid działa
Ponieważ mid może być odpowiedzią, nie wolno go pomijać. Użycie high = mid pozostawia mid w zakresie, a jednocześnie nadal go zmniejsza, gwarantując postęp.
high = mid # mid stays a candidatePrzykład pierwiastka całkowitego
Aby znaleźć największe x spełniające x*x nie większe niż n, wyszukaj pierwszą wartość true dla warunku x*x > n, a następnie cofnij się o jeden. Ten schemat można wielokrotnie stosować.
def ok(x):
return x * x > n
# answer is found_index - 1Jeden schemat, wiele problemów
Ten schemat first-true rozwiązuje niezliczone zadania: znalezienie minimalnej wykonalnej wartości, skrajnego lewego indeksu czy najmniejszej pojemności. Naucz się go raz i wykorzystuj wszędzie.
# low<high, ok->high=mid, else low=mid+1Szybkie sprawdzenie
Wskaż krok, który pozwala zachować kandydata.
Podsumowanie: znaleziono pierwszą wartość true
Potrafisz już przekształcić problem w predykat monotoniczny i wyszukać binarnie jego granicę. high = mid wraz z while low < high to bezpieczny schemat. 🧭
Często zadawane pytania
Czy lekcja „Pierwsza wartość True: wyszukiwanie binarne predykatu” jest bezpłatna?
Tak — pełny tekst „Pierwsza wartość True: wyszukiwanie binarne predykatu” 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 „Pierwsza wartość True: wyszukiwanie binarne predykatu”?
Wyszukiwanie monotonicznej granicy tak/nie Ć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 3 z 4.
Ile czasu zajmuje lekcja „Pierwsza wartość True: wyszukiwanie binarne predykatu”?
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