Algorithmusgymnastik 3

Search Rotated Array Ein sortiertes Array, das um eine beliebige Zahl nach rechts gedreht wurde, und die angegebene Zahl (Schlüssel) werden übergeben und durchsucht.

Erläuterung

Findet die angegebene Nummer (Schlüssel) in einem sortierten Array, das um eine beliebige Nummer gedreht wurde. Gibt -1 zurück, wenn der Schlüssel nicht vorhanden ist. Angenommen, das Array enthält keine Duplikate. Unten ist das ursprüngliche Array vor der Drehung. Wenn Sie die Rotation 6 Mal in diesem Array ausführen, ändert sich dies wie folgt.

Bedingungen

1. Die lineare Suche O (n) ist eine inakzeptable Lösung.
2. Betrachten Sie die geänderte binäre Suche.

Solution Runtime Complexity O(logn) Ich verwende die binäre Suche. Memory Complexity O(logn). Für jede Schleife wird das übergebene Array halbiert und nur eines durchsucht.

Kommentar

Die Lösung ist im Grunde binäre Suche, aber mit einigen Korrekturen. Wenn Sie sich das Beispielarray genau ansehen, sehen Sie, dass immer mindestens die Hälfte des Arrays sortiert ist. Nutzen Sie diese Funktion. Wenn sich die gesuchte Nummer n in der sortierten Hälfte des Arrays befindet, können Sie sie mit der binären Suche finden. Andernfalls verwerfen Sie die sortierten Hälften und untersuchen Sie die unsortierten Hälften weiter. Dies teilt das Array bei jedem Schritt in zwei Hälften, wodurch die Laufzeitkomplexität O (logn) wird. Es gibt einige bedingte Teile des Codes, die etwas schwer zu lesen sind. Unter vier Bedingungen

1. Wenn das SubArray im Bereich von Start bis Mitte in zwei Hälften geschnitten ** sortiert ** ist und der gesuchte Schlüssel in diesem Bereich vorhanden ist.
2. Wenn das SubArray im Bereich von Mitte bis Ende halbiert ** sortiert ** ist und der gesuchte Schlüssel in diesem Bereich vorhanden ist.
3. Wenn das SubArray im Bereich von Start ~ Mid Cut in zwei Hälften nicht ** sortiert ** ist und der gesuchte Schlüssel in diesem Bereich vorhanden ist.
4. Wenn das SubArray im Bereich von Mitte bis Ende, das in zwei Hälften geschnitten wird, nicht ** sortiert ** ist und der gesuchte Schlüssel in diesem Bereich vorhanden ist. Die Bedingungen sind als solche unterteilt.

Implementierung

Prüfung

Ausgabe