Algorithmen und Datenstrukturen · Middle · Frage 16 von 75
Wie findet man in O(log n) einen Wert in einem rotierten sortierten Array wie [4, 5, 6, 1, 2, 3]?
- 1Lineare Suche, weil die Rotation die Ordnung bricht
- 2Binäre Suche, bei jedem Schritt prüfen, welche Hälfte sortiert ist
- 3Erst das Array sortieren, dann normal binär suchen
Antwort zeigen
Richtige Antwort: Binäre Suche, bei jedem Schritt prüfen, welche Hälfte sortiert ist
Erklärung
Vergleiche arr[lo] mit arr[mid], um zu sehen, welche Hälfte geordnet ist, und prüfe dann, ob das Ziel in den Bereich dieser Hälfte fällt. Vorher zu sortieren kostet O(n log n), lineare Suche O(n).