Wyszukiwanie binarne w przestrzeni odpowiedzi
Potraktują Państwo ciągły zakres odpowiedzi jako przestrzeń wyszukiwania, aby rozwiązywać problemy takie jak minimum-time-to-complete-jobs i capacity-to-ship-packages.
Wyszukiwanie binarne w przestrzeni odpowiedzi to bezpłatna lekcja DSA 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Wyszukiwanie binarne w przestrzeni odpowiedzi
Większość osób zna wyszukiwanie binarne służące do znajdowania wartości w posortowanej tablicy. Wyszukiwanie binarne jest jednak jeszcze bardziej przydatne, gdy stosuje się je do przestrzeni możliwych odpowiedzi. Zamiast przeszukiwać tablicę, przeszukuje się zakres liczbowy — na przykład odpowiadając na pytanie: „jaka jest minimalna liczba dni potrzebna do wysłania wszystkich paczek?” — i używa funkcji sprawdzającej, aby określić, czy dana odpowiedź jest wykonalna.
Technika ta pozwala przekształcić wiele problemów optymalizacyjnych o złożoności O(n²) lub większej w problemy o złożoności O(n log(max_answer)).
Wzorzec dla przestrzeni odpowiedzi
Szablon składa się z trzech elementów. Po pierwsze należy określić zakres wyszukiwania [lo, hi], który obejmuje wszystkie poprawne odpowiedzi. Po drugie należy napisać sprawdzenie wykonalności can_achieve(mid), zwracające True, jeśli wartość mid jest osiągalna. Po trzecie należy wykonać wyszukiwanie binarne w zakresie [lo, hi]: jeśli can_achieve(mid) zwraca True, przesuwamy się w stronę mniejszej (lub większej) odpowiedzi; w przeciwnym razie przesuwamy się w drugą stronę.
Kluczowa właściwość jest następująca: funkcja wykonalności musi być monotoniczna — gdy dana odpowiedź jest wykonalna, wszystkie wartości znajdujące się dalej w tym kierunku również są wykonalne (lub wszystkie wartości po drugiej stronie są niewykonalne).
# Generic template
def answer_space_search(lo, hi, is_feasible):
result = hi # or lo, depending on direction
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
hi = mid - 1 # try to minimise further
else:
lo = mid + 1
return resultPrzykład: pojemność wysyłkowa paczek
LeetCode 1011 „Pojemność wysyłkowa paczek w ciągu D dni”: mając listę wag oraz D dni, należy znaleźć minimalną pojemność wysyłkową, która pozwoli wysłać wszystkie paczki w podanej kolejności w ciągu D dni. Odpowiedź znajduje się w przedziale [max(weights), sum(weights)]. Dana pojemność jest wykonalna, jeśli zachłanna symulacja pozwala wysłać wszystkie paczki w ciągu D dni. Wyszukiwanie binarne w zakresie pojemności daje złożoność czasową O(n log(sum)).
def shipWithinDays(weights, days):
def can_ship(capacity):
needed_days, current_load = 1, 0
for w in weights:
if current_load + w > capacity:
needed_days += 1
current_load = 0
current_load += w
return needed_days <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_ship(mid):
hi = mid # feasible, try smaller
else:
lo = mid + 1 # not feasible, need more capacity
return lo
print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(shipWithinDays([3,2,2,4,1,4], 3)) # 6Przykład: jedzenie bananów przez Kokę
LeetCode 875 „Jedzenie bananów przez Kokę”: Koka może zjadać K bananów na godzinę; chce zjeść H stosów w dokładnie H godzin, minimalizując K. Zakres wyszukiwania to [1, max(piles)]. Sprawdzenie polega na obliczeniu: przy tempie K łączna liczba godzin = sum(ceil(pile/K)), która musi być <= H. Wyszukujemy binarnie najmniejsze K spełniające ten warunek.
import math
def minEatingSpeed(piles, h):
def can_finish(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_finish(mid):
hi = mid # feasible, try lower speed
else:
lo = mid + 1 # too slow
return lo
print(minEatingSpeed([3,6,7,11], 8)) # 4
print(minEatingSpeed([30,11,23,4,20], 5)) # 30Przykład: minimalna liczba dni potrzebna do przygotowania bukietów
LeetCode 1482 „Minimalna liczba dni potrzebna do przygotowania m bukietów”: potrzebują Państwo m bukietów, z których każdy składa się z k kolejnych kwiatów, które rozkwitły. Kwiat i rozkwita w dniu bloomDay[i]. Wyszukujemy binarnie dzień: zakres to [1, max(bloomDay)]. Sprawdzenie wykonalności zlicza kolejne rozkwitłe kwiaty i sprawdza, czy można z nich utworzyć m bukietów. Własność monotoniczna: jeśli rozwiązanie działa dla dnia d, to działa również dla dnia d+1.
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1 # impossible
def can_make(day):
bouquets = consecutive = 0
for bd in bloomDay:
if bd <= day:
consecutive += 1
if consecutive == k:
bouquets += 1
consecutive = 0
else:
consecutive = 0
return bouquets >= m
lo, hi = 1, max(bloomDay)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_make(mid):
hi = mid
else:
lo = mid + 1
return lo
print(minDays([1,10,3,10,2], 3, 1)) # 3
print(minDays([1,10,3,10,2], 3, 2)) # -1Określanie zakresu wyszukiwania
Wybór właściwego zakresu [lo, hi] ma kluczowe znaczenie. lo powinno oznaczać najmniejszą możliwą odpowiedź (na przykład najmniejszy element, 1 lub 0), a hi — największą możliwą odpowiedź (na przykład sumę wszystkich elementów, największy element lub n). Ustawienie zbyt małej wartości hi powoduje pominięcie poprawnych odpowiedzi; zbyt duża wartość nie stanowi problemu, ponieważ wyszukiwanie binarne i tak zbiegnie w O(log(hi - lo)) krokach.
# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating: lo=1, hi=max(piles)
# Square root: lo=1, hi=x
# Allocate books: lo=max(pages), hi=sum(pages)
def isqrt_bs(x):
if x < 2:
return x
lo, hi = 1, x
while lo < hi:
mid = lo + (hi - lo) // 2
if mid * mid <= x:
lo = mid + 1
else:
hi = mid
return lo - 1
for n in [0, 1, 4, 8, 9, 15, 16]:
print(f'isqrt({n}) = {isqrt_bs(n)}')Maksymalizowanie a minimalizowanie: kierunek ma znaczenie
Wyszukiwanie binarne po przestrzeni odpowiedzi występuje w dwóch wariantach. Minimalizowanie odpowiedzi: gdy sprawdzenie się powiedzie, należy spróbować mniejszej wartości (hi = mid); gdy się nie powiedzie, należy spróbować większej (lo = mid + 1). Maksymalizowanie odpowiedzi: gdy sprawdzenie się powiedzie, należy spróbować większej wartości (lo = mid + 1, zapisując mid jako kandydata); gdy się nie powiedzie, należy spróbować mniejszej (hi = mid - 1). Przed rozpoczęciem implementacji należy zawsze określić, w którym kierunku odbywa się wyszukiwanie.
# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
result = lo - 1 # sentinel: no feasible answer found
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
lo = mid + 1 # try larger
else:
hi = mid - 1
return result
# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50)) # 7Przydzielanie minimalnej liczby stron (klasyczny problem)
Mając n książek z tablicą pages[] oraz k uczniami, należy przydzielić książki w sposób ciągły tak, aby uczeń czytający najwięcej stron przeczytał ich możliwie najmniej. Wyszukujemy binarnie odpowiedź (minimalną możliwą wartość maksymalną). Sprawdzenie wykonalności zachłannie przydziela książki uczniom: gdy dodanie książki przekroczyłoby bieżącą wartość maksymalną, książka zostaje przydzielona nowemu uczniowi. Jeśli liczba potrzebnych uczniów jest <= k, dana wartość maksymalna jest osiągalna.
def allocate_min_pages(pages, k):
if k > len(pages):
return -1
def is_feasible(max_pages):
students, current = 1, 0
for p in pages:
if p > max_pages:
return False # single book exceeds limit
if current + p > max_pages:
students += 1
current = 0
current += p
return students <= k
lo, hi = max(pages), sum(pages)
while lo < hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
print(allocate_min_pages([12, 34, 67, 90], 2)) # 113
print(allocate_min_pages([10, 20, 30, 40], 2)) # 60Analiza złożoności wyszukiwania po przestrzeni odpowiedzi
Złożoność czasowa wynosi O(n × log(range)), gdzie n oznacza koszt sprawdzenia wykonalności (zwykle jest to liniowe przejście), a range = hi - lo oznacza rozmiar przestrzeni odpowiedzi. Na przykład jeśli suma stron wynosi 10⁹, a sprawdzenie wykonalności ma złożoność O(n), całkowity czas wynosi O(n log 10⁹) ≈ O(30n), co jest znacznie lepsze niż brutalne sprawdzanie wszystkich możliwości w czasie O(n²).
Złożoność pamięciowa samego wyszukiwania binarnego wynosi O(1), powiększone o pamięć używaną przez sprawdzenie wykonalności.
import math
# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9 # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9) # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')K-ty najmniejszy element w posortowanej macierzy
LeetCode 378 „K-ty najmniejszy element w posortowanej macierzy”: każdy wiersz i każda kolumna macierzy n×n są posortowane. Wyszukujemy binarnie wartość odpowiedzi w przedziale [matrix[0][0], matrix[n-1][n-1]]. Sprawdzenie wykonalności zlicza elementy <= mid za pomocą wskaźnika rozpoczynającego pracę w lewym dolnym rogu; działa ono w czasie O(n). Należy znaleźć najmniejszą wartość, dla której co najmniej k elementów jest <= mid.
def kthSmallest(matrix, k):
n = len(matrix)
def count_le(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if count_le(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8)) # 13Rozpoznawanie problemów dotyczących przestrzeni odpowiedzi
Problemy odpowiednie do wyszukiwania binarnego po przestrzeni odpowiedzi mają wspólne cechy: pytanie dotyczy wartości minimalnej lub maksymalnej, odpowiedź znajduje się w ograniczonym zakresie liczbowym, a zwiększanie (lub zmniejszanie) wartości kandydata sprawia, że wykonalność staje się monotonicznie lepsza lub gorsza. Typowe sformułowania to „najmniejsza możliwa wartość maksymalna”, „co najwyżej k operacji” oraz „w ciągu d dni”.
Po rozpoznaniu tych sygnałów należy od razu określić lo i hi, napisać funkcję sprawdzającą wykonalność i zastosować szablon. Takie uporządkowane podejście rzadko zawodzi podczas rozmów kwalifikacyjnych.
Szybki test
Sprawdź swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: wyszukiwanie binarne po przestrzeni odpowiedzi stosuje się, gdy funkcja wykonalności jest monotoniczna w pewnym zakresie liczbowym, szablon przeszukuje przedział [lo, hi] i za pomocą sprawdzenia can_achieve zmniejsza przestrzeń wyszukiwania o połowę, a całkowita złożoność wynosi O(n log(range)), gdzie n jest kosztem pojedynczego sprawdzenia wykonalności. W następnej części przejdziemy do list wiązanych i klasy Node.
Często zadawane pytania
Czy lekcja „Wyszukiwanie binarne w przestrzeni odpowiedzi” jest bezpłatna?
Tak — pełny tekst „Wyszukiwanie binarne w przestrzeni 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Wyszukiwanie binarne w przestrzeni odpowiedzi”?
Potraktują Państwo ciągły zakres odpowiedzi jako przestrzeń wyszukiwania, aby rozwiązywać problemy takie jak minimum-time-to-complete-jobs i capacity-to-ship-packages. Ćwiczysz DSA 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ąć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA 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 w przestrzeni 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 DSA Interview Prep?
Tak. Każda lekcja DSA 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
- Klasyczne wyszukiwanie binarne: lewo, prawo, środek
- Wyszukiwanie binarne w tablicach obróconych i nieposortowanych
- Dolna i górna granica
- Wyszukiwanie binarne w przestrzeni odpowiedzi