Quelle: Microsoft-Interviewfrage
Bei einem sortierten Array, in dem jedes Element zweimal vorhanden ist, mit Ausnahme eines Elements, das nur einmal vorhanden ist, müssen wir dieses Element finden.
Eine Standard-O (n) -Lösung besteht nun darin, eine XOR-Liste zu erstellen, die das nicht duplizierte Element zurückgibt (da alle duplizierten Elemente ausgelöscht werden).
Ist es möglich, dies schneller zu lösen, wenn wir wissen, dass das Array sortiert ist?
Ja, Sie können die Sortierung verwenden, um die Komplexität auf O(log n) zu reduzieren, indem Sie eine binäre Suche durchführen.
Da das Array vor dem fehlenden Element sortiert ist, belegt jeder Wert die Punkte 2*k und 2*k+1 im Array (bei 0-basierter Indizierung vorausgesetzt).
Sie gehen also in die Mitte des Arrays, sagen den Index h , und überprüfen entweder den Index h+1 , wenn h gerade ist, oder h-1 , wenn h ungerade ist. Wenn das fehlende Element später kommt, sind die Werte an diesen Positionen gleich, wenn es vorher kommt, sind die Werte unterschiedlich. Wiederholen Sie dies, bis das fehlende Element gefunden wurde.
Machen Sie eine binäre "Suche" (eher Traversal) auf dem Array, überprüfen Sie beide Nachbarn, wenn beide von dem Wert in der Mitte abweichen, haben Sie die Lösung. Das ist O(log n) .
Tags und Links algorithm arrays complexity-theory