0Pricing
Coding Interview Prep · Lekcja

Wyszukiwanie binarne po odpowiedzi

Zgadywanie wyniku i sprawdzanie wykonalności

Wyszukiwanie binarne po odpowiedzi to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 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.

Zgadnij, a następnie sprawdź

Czasami nie da się bezpośrednio obliczyć odpowiedzi, ale można sprawdzić przypuszczenie. Wyszukiwanie binarne po odpowiedzi zamienia trudną optymalizację w łatwe sprawdzanie.

# guess X, ask: is X feasible?

Magiczna własność

Metoda działa, gdy wykonalność jest monotoniczna: jeśli dana wartość działa, każda większa (lub mniejsza) wartość również działa. To uporządkowanie jest właśnie przedmiotem wyszukiwania.

# feasible(X) true => feasible(X+1) true

Ogranicz zakres odpowiedzi

Wyznacz najmniejszą i największą możliwą odpowiedź jako low i high. Dla minimalnej pojemności low to jeden element, a high to suma wszystkich elementów.

low, high = max(weights), sum(weights)

Napisz sprawdzanie wykonalności

Sercem metody jest funkcja can(X), która zwraca true, jeśli przypuszczenie X jest osiągalne. Zwykle działa ona w czasie liniowym.

def can(cap):
    # simulate and return True/False
    ...

Przykład: wysyłka w D dni

Przy danej dziennej pojemności cap zachłannie zapełniaj kolejne dni i je licz. can(cap) zwraca true, gdy liczba dni mieści się w limicie D.

def can(cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days <= D

Znajdź minimalną pojemność

Szukasz najmniejszej wartości cap, która przejdzie sprawdzenie. Jest to wyszukiwanie first-true po wartościach pojemności, więc ponownie użyj schematu high = mid.

while low < high:
    mid = (low + high) // 2

Zachowaj wykonalną połowę

Jeśli can(mid) zwraca true, mniejsza pojemność również może wystarczyć, więc ustaw high = mid. W przeciwnym razie podnieś dolną granicę za pomocą low = mid + 1.

if can(mid):
    high = mid
else:
    low = mid + 1

Pamiętaj o limicie czasu

Łączny koszt to O(check x log range). Liniowe sprawdzenie zakresu o szerokości miliarda wymaga tylko około 30 sprawdzeń, więc wystarcza nawet przy ścisłych limitach.

# log2(1e9) is about 30 iterations

Maksymalizuj zamiast minimalizować

Aby znaleźć największą wykonalną wartość, odwróć logikę: wyszukuj ostatnią wartość true. Gdy wartość jest wykonalna, zwiększaj low, a gdy nie jest — zmniejszaj high.

if can(mid):
    low = mid
else:
    high = mid - 1

Odpowiedzi rzeczywiste

W przypadku odpowiedzi zmiennoprzecinkowych wykonaj stałą liczbę iteracji, na przykład 100, zamiast obliczać całkowite mid. Każda runda zmniejsza przedział o połowę, szybko osiągając bardzo małą dokładność.

for _ in range(100):
    mid = (low + high) / 2

Rozpoznawanie schematu

Sformułowania takie jak „minimum z maksimów”, „maksimum z minimów” lub „najmniejsze k, które działa” to sygnały, że warto zastosować wyszukiwanie binarne po odpowiedzi. Warto wyćwiczyć ich rozpoznawanie.

# 'minimize the maximum' => search answer

Szybkie sprawdzenie

Ustal, kiedy można zastosować wyszukiwanie binarne po odpowiedzi.

Podsumowanie: wyszukiwanie odpowiedzi

Potrafisz już ograniczyć zakres odpowiedzi, napisać sprawdzanie wykonalności i wyszukać binarnie minimum lub maksimum. Trudne problemy stają się zgadywaniem i weryfikacją. 🏆

Często zadawane pytania

Czy lekcja „Wyszukiwanie binarne po odpowiedzi” jest bezpłatna?

Tak — pełny tekst „Wyszukiwanie binarne po odpowiedzi” 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 „Wyszukiwanie binarne po odpowiedzi”?

Zgadywanie wyniku i sprawdzanie wykonalności Ć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 4 z 4.

Ile czasu zajmuje lekcja „Wyszukiwanie binarne po odpowiedzi”?

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