Algorytmy i struktury danych · Middle · Pytanie 15 z 75
Co oznacza „wyszukiwanie binarne po odpowiedzi”?
- 1Wyszukiwanie binarne w tablicy odpowiedzi od użytkowników
- 2Sprawdzanie każdej możliwej odpowiedzi od 1 do n, aż któraś pasuje
- ✓Poprawna odpowiedź: Szukanie najmniejszej wartości spełniającej monotoniczny test
Wyjaśnienie
Jeśli „czy da się to zrobić z x?” jest fałszywe do pewnego momentu i prawdziwe po nim, x można szukać binarnie. Przykład: minimalna ładowność statku, aby dostarczyć paczki w D dni, gdzie każde sprawdzenie to zachłanne przejście O(n).