Dans le chapitre 3-3 Recherche de deux minutes du livre "Algorithmes et structures de données Java nouveaux et clairs", il y avait une norme à retenir lors de l'écriture de Java, je vais donc la résumer dans cet article en incluant la recherche de deux minutes. C'était.
Java fournit une bibliothèque standard de méthodes pour dichotomiser un tableau.
Une méthode binarySearch qui appartient à la classe java.util.Arrays.
Référence: https://docs.oracle.com/javase/jp/8/docs/api/java/util/Arrays.html
Comme vous pouvez le voir dans le lien de référence ci-dessus, de nombreuses méthodes binarySearch sont définies pour prendre en charge divers types d'éléments. Les deux dichotomisent les éléments de valeur clé du tableau trié ascendant (les résultats ne sont pas définis s'ils ne sont pas ascendants).
S'il existe une clé de recherche dans le tableau, l'index de la clé de recherche est renvoyé, et si elle n'existe pas, (- (point d'insertion) -1) est renvoyé.
Cette fois, nous nous concentrerons sur les deux points suivants.
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) Jugez la relation de grandeur des éléments dans un ordre naturel. Veuillez vous référer à ce qui suit pour une commande naturelle.
Référence: https://docs.oracle.com/javase/jp/8/docs/api/java/lang/Comparable.html
Si vous avez un tableau de types qui implémente l'interface Comparable dans le lien de référence ci-dessus, vous pouvez facilement écrire du code pour faire une dichotomie en utilisant cette méthode.
En d'autres termes, même pour votre propre classe, vous pouvez définir un ordre naturel en implémentant cette interface Comparable, et vous pouvez utiliser cette méthode. C'est une bonne idée de se souvenir de ce qui suit comme un petit standard.
Classe naturellement ordonnée.java
public class Hoge implements Comparable<Hoge> {
//Champs, méthodes, etc.
@Override
public int compareTo(A c) {
//Si c'est supérieur à c, une valeur positive,
//Si c'est inférieur à c, une valeur négative,
//Renvoie 0 si c'est égal à c.
}
@Override
public boolean equals(Object c) {
//Vrai si c'est égal à c,
//Renvoie false si ce n'est pas égal à c.
}
}
À ce stade, la cohérence peut être obtenue comme "lorsque la méthode conpareTo retourne 0, la méthode ʻequals retourne true, et lorsque la méthode compareTo retourne une valeur non nulle, la méthode ʻequals retourne false ". Ce serait bien de le faire.
static
Cependant, vous devez indiquer à la méthode comment déterminer la relation de grandeur de chaque élément. Pour ce faire, passez une instance de la classe qui implémente l'interface java.util.Comparator comme troisième argument.
Par exemple, un comparateur de classe Fuga peut être défini comme: C'est une bonne idée de se souvenir de cela comme un petit standard.
Définir un comparateur à l'intérieur de la classe.java
public class Fuga {
//Champs, méthodes, etc.
public static final Comparator<Fuga> COMPARATOR = new Comp();
private static class Comp implements Comparator<Fuga> {
public int compare(Fuga d1, Fuga d2) {
//Si d1 est supérieur à d2, alors une valeur positive,
//Valeur négative si d1 est inférieur à d2,
//Renvoie 0 si d1 est égal à d2.
}
}
}
En passant «Fuga.COMPARATOR» comme troisième argument de la méthode «binarySearch», la relation de grandeur peut être déterminée en fonction du comparateur défini, et une dichotomie du tableau de type «Fuga» peut être effectuée.
Recommended Posts