Aus dem Buch "Neue und klare Java-Algorithmen und Datenstrukturen", Kapitel 3-3, zweiminütige Suche, gab es einen Standard, den Sie beim Schreiben von Java beachten sollten. Daher werde ich ihn in diesem Artikel zusammenfassen, einschließlich der zweiminütigen Suche. Es war.
Java bietet eine Standardbibliothek von Methoden zum Dichotomisieren eines Arrays.
Eine binarySearch Methode, die zur java.util.Arrays Klasse gehört.
Referenz: https://docs.oracle.com/javase/jp/8/docs/api/java/util/Arrays.html
Wie Sie im obigen Referenzlink sehen können, sind viele "binarySearch" -Methoden definiert, um verschiedene Elementtypen zu unterstützen. Beide dichotomisieren die Schlüsselwertelemente aus dem aufsteigenden sortierten Array (Ergebnisse sind undefiniert, wenn sie nicht aufsteigen). Wenn das Array einen Suchschlüssel enthält, wird der Index des Suchschlüssels zurückgegeben, und wenn er nicht vorhanden ist, wird (- (Einfügemarke) -1) zurückgegeben.
Dieses Mal konzentrieren wir uns auf die folgenden zwei Punkte.
static int binarySearch(Object[] a, Object key)
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
static int binarySearch(Object[] a, Object key) Beurteilen Sie das Größenverhältnis von Elementen in einer natürlichen Reihenfolge. Bitte beachten Sie die folgenden Informationen zur natürlichen Bestellung.
Referenz: https://docs.oracle.com/javase/jp/8/docs/api/java/lang/Comparable.html
Wenn Sie über ein Array von Typen verfügen, das die Schnittstelle "Comparable" im obigen Referenzlink implementiert, können Sie mit dieser Methode problemlos Code schreiben, um eine Dichotomie durchzuführen.
Mit anderen Worten, selbst für Ihre eigene Klasse können Sie die natürliche Reihenfolge definieren, indem Sie diese "Vergleichbare" Schnittstelle implementieren, und Sie können diese Methode verwenden. Es ist eine gute Idee, sich an Folgendes als kleinen Standard zu erinnern.
Natürlich geordnete Klasse.java
public class Hoge implements Comparable<Hoge> {
//Felder, Methoden usw.
@Override
public int compareTo(A c) {
//Wenn dies größer als c ist, ein positiver Wert,
//Wenn dies kleiner als c ist, ein negativer Wert,
//Gibt 0 zurück, wenn dies gleich c ist.
}
@Override
public boolean equals(Object c) {
//Richtig, wenn dies gleich c ist,
//Gibt false zurück, wenn dies nicht gleich c ist.
}
}
Zu diesem Zeitpunkt kann Konsistenz erhalten werden, z. B. "Wenn die" conpareTo "-Methode 0 zurückgibt, gibt die" equals "-Methode true zurück, und wenn die" compareTo "-Methode ungleich Null zurückgibt, gibt die" equals "-Methode false zurück". Es wäre gut, dies zu tun.
static
Sie müssen der Methode jedoch mitteilen, wie die Größenbeziehung jedes Elements bestimmt werden soll. Übergeben Sie dazu eine Instanz der Klasse, die die Schnittstelle java.util.Comparator als drittes Argument implementiert.
Ein Klassen-Fuga-Komparator kann beispielsweise wie folgt definiert werden: Es ist eine gute Idee, sich daran als kleinen Standard zu erinnern.
Definieren Sie einen Komparator innerhalb der Klasse.java
public class Fuga {
//Felder, Methoden usw.
public static final Comparator<Fuga> COMPARATOR = new Comp();
private static class Comp implements Comparator<Fuga> {
public int compare(Fuga d1, Fuga d2) {
//Wenn d1 größer als d2 ist, dann ist ein positiver Wert,
//Negativer Wert, wenn d1 kleiner als d2 ist,
//Gibt 0 zurück, wenn d1 gleich d2 ist.
}
}
}
Durch Übergabe von "Fuga.COMPARATOR" als drittes Argument der "binarySearch" -Methode kann die Größenbeziehung basierend auf dem definierten Komparator bestimmt und eine Dichotomie des Arrays vom Typ "Fuga" durchgeführt werden.
Recommended Posts