Algorithmen und Datenstrukturen · Middle · Frage 15 von 75
Was bedeutet „binäre Suche über die Antwort“?
- 1Binäre Suche über ein Array von Antworten von Nutzern laufen lassen
- 2Jede mögliche Antwort von 1 bis n prüfen, bis eine passt
- 3Den kleinsten Wert suchen, der einen monotonen Test besteht
Antwort zeigen
Richtige Antwort: Den kleinsten Wert suchen, der einen monotonen Test besteht
Erklärung
Ist „geht es mit x?“ bis zu einem Punkt false und danach true, kann man x binär suchen. Beispiel: die minimale Schiffskapazität, um Pakete in D Tagen zu liefern, wobei jede Prüfung ein Greedy-Durchlauf in O(n) ist.