Angenommen, ich habe eine Java ArrayList, die sortiert ist. Jetzt möchte ich den Index des Wertes x finden. Was wäre der schnellste (ohne mehr als 30 Zeilen Code) Weg, dies zu tun? Verwendung der IndexOf() Methode? Durch alle Werte in einer einfachen for-Schleife? Verwendung eines coolen Algorithmus? Wir sprechen von etwa 50 ganzzahligen Schlüsseln.Der beste Weg, um Wert in Liste zu finden, wenn die Liste sortiert ist
Binary search, aber da es nur 50 Elemente sind, wen interessiert es (es sei denn, Sie müssen es millionenfach tun)? Eine einfache lineare Suche ist einfacher und der Leistungsunterschied für 50 Elemente ist vernachlässigbar.
Bearbeiten: Sie können auch die integrierte Methode java.util.Collections binarySearch verwenden. Beachten Sie, dass ein Einfügepunkt zurückgegeben wird, auch wenn das Element nicht gefunden wird. Möglicherweise müssen Sie einige zusätzliche Überprüfungen durchführen, um sicherzustellen, dass der Artikel wirklich der gewünschte ist. Danke an @Matthew für den Zeiger.
tvanfosson hat Recht, dass die Zeit für beide sehr niedrig sein wird, also wenn dieser Code nicht sehr häufig läuft, wird es keinen großen Unterschied machen.
Java verfügt jedoch über integrierte Funktionen für die Binärsuche von Listen (einschließlich ArrayLists), Collections.binarySearch.
Wenn die Schlüssel eine akzeptable Verteilung haben, kann Interpolation Search sehr schnelle Weise sein, die Ausführungszeit denkend.
In Anbetracht Codierungszeit IndexOf() ist der Weg zu gehen (oder eine eingebaute binäre Suche, wenn für Ihren Datentyp verfügbar (ich bin von C# und weiß nicht, Java)).
import java.util.ArrayList;
import java.util.Collections;
ArrayList myList = new ArrayList();
// ...fill with values
Collections.sort(myList);
int index = Collections.binarySearch(myList, "searchVal");
Edit: ungetesteten Code
Danke für den Code :) – Baversjo
Für fünfzig Tasten stimme ich vollständig. Die Entwicklerzeit ist heutzutage wichtiger als die CPU-Zeit. Verwenden Sie IndexOf() und machen Sie sich auf den Weg. –
Außer dass Java/diese Funktionalität hat. –
Binäre Suche ist der Weg zu gehen. Die Liste kann derzeit nur 50 Elemente haben, aber wer weiß, was der Code in einem Jahr oder zwei zu handhaben haben wird. –