Recherche binaire en java

La recherche d'un tableau pour la position d'une valeur et le tri du tableau, sont deux processus différents. La recherche signifie vérifier si une valeur appelée la clé est trouvée dans le tableau. Le tri signifie mettre toutes les valeurs dans le tableau dans un ordre particulier (ascendant ou descendant). Si un tableau n'est pas trié et que la recherche est requise, le programme doit commencer par l'index zéro, puis à l'index 1, alors index 2, et ainsi de suite, jusqu'à ce qu'il atteigne l'index de la valeur qu'il recherche. Si la valeur se produit plus d'une fois, le premier index doit être renvoyé.

Si le tableau est trié en premier, disons par ordre croissant, la recherche devient facile. L'indice est inférieur à l'index de l'élément central, si la clé est inférieure à la valeur de l'index moyen, ou que l'index est égal ou supérieur à celui de l'index moyen, si la valeur est égale ou supérieure à celui de la valeur d'index moyen.

Alors divise le tableau en deux. Si la valeur se trouve sur le côté gauche, pas besoin de perdre du temps à rechercher le côté droit; Recherchez simplement le côté gauche. Si la valeur se trouve sur le côté droit, pas besoin de perdre du temps à rechercher le côté gauche; Recherchez simplement le côté droit. Étant donné que le tableau est déjà complètement trié, lorsque les deux côtés sont arrivés, il est à nouveau divisé en deux, et une seule des nouvelles paires de côtés est fouillée. En fait, la recherche de cette façon est simplement en divisant en deux, jusqu'à ce que l'index de la valeur soit arrivé à. Aucune recherche réelle en termes de numérisation n'a lieu car le tableau est déjà trié. Il peut y avoir un léger déménagement à droite, et un léger mouvement à gauche dans le tableau pendant la recherche.

Le binaire implique, deux. Et donc ce type de recherche s'appelle la recherche binaire. Il existe différentes commandes de tri: toutes les valeurs du tableau peuvent être triées en ordre croissant ou en complètement l'ordre descendant. Un tableau peut également être trié dans ce qui est connu sous le nom de format d'arbre de recherche binaire. Ce n'est pas un tri complet dans l'ordre croissant ou descendant. Cependant, la recherche d'algorithme binaire fonctionne toujours avec ce format.

Cet article explique la recherche binaire Java. L'algorithme de recherche binaire dans Java fonctionne sur un tableau déjà trié. Seul le tri complet dans l'ordre croissant est considéré dans cet article. Cet article commence par l'illustration de l'algorithme de recherche binaire. Il explique ensuite comment utiliser les méthodes BinarySearch () de la classe Java Arrays.

Contenu de l'article

• Illustration de l'algorithme de recherche binaire
• Package Java et classe pour la recherche binaire
• Construire le tableau de recherche
• Méthodes de recherche binaire de la classe des tableaux
• Recherche d'une plage
• Conclusion

Illustration de l'algorithme de recherche binaire

Considérez la séquence de caractères suivante:

P v d q s x t h n o

Arrangeant par ordre croissant, la séquence devient:

D h n o p q s t v x

Il y a dix éléments ici. Le comptage d'index commence à partir de 0. Lorsque le nombre d'éléments est uniforme (e.g., 10), l'indice de l'élément central est considéré comme le nombre d'éléments divisés par deux. Dans ce cas, 10/2 est 5. Lorsque le nombre d'éléments est impair, l'index pour l'élément central est considéré comme la partie entière (nombre entier) du nombre d'éléments divisé par deux.

Il y a deux listes ci-dessus. Le second est la forme triée du premier. Supposons que la recherche devait savoir si S était présent dans la première liste. La liste devrait d'abord être triée pour avoir la deuxième liste du schéma de recherche binaire. Dans la liste triée, l'index pour la position moyenne est de 5 = 10/2. Cela correspond à la valeur, q. La recherche s'arrête alors pour vérifier si q est s, la valeur recherchée. Si c'est le cas, alors la recherche s'arrête. Si ce n'est pas le cas, la recherche vérifie si S se trouve moins de q ou de Q vers le haut.

Dans ce cas, il réside dans la plage de Q vers le haut, qui est ensuite choisi. Aucun temps ne sera perdu en cherchant la moitié inférieure de la liste (tableau). Donc, cette nouvelle gamme doit être divisée en deux. Cette gamme se compose de 5 éléments. 5/2 = 2 et un 1/2. L'élément central est en position 2 de cette nouvelle gamme. Cela correspond à t, si le comptage de zéro est de commencer à partir de q. L'indice réel de t est 7.

La plage inférieure ou gauche se compose désormais de (q s), tandis que la nouvelle gamme supérieure ou droite se compose désormais de (t v x). Est le nouvel élément central, T du même que S, la valeur recherchée? - Non. Dans quelle gamme se trouve S; est-ce dans la plage inférieure, (q s) ou dans la plage supérieure, (t v x)? - Il se trouve dans la gamme inférieure.

Ainsi, la gamme inférieure (Q S) doit alors être divisée en deux. Lorsque cela est fait, l'index moyen de cette plage correspond à S (2/2 = 1, car q est à nouvel index 0). L'indice réel pour S est de 6 (D est à l'index d'origine 0). L'indice de la valeur trouvée doit être renvoyé.

Clé introuvable

La valeur recherchée est appelée la clé. La liste triée a en fait deux indextes comme indiqué ci-dessous:

D	H	N	O	P	Q	S	T	V	X
0	1	2	3	4	5	6	7	8	9
-1	-2	-3	-4	-5	-6	-7	-8	-9	-dix

La première ligne de ce tableau a la liste triée. La deuxième ligne a l'indexation normale. La troisième ligne a une sorte d'indexation négative où le premier élément est à l'index -1, le second est à l'index -2, le troisième à l'index -3, etc.

Si la clé est trouvée, l'algorithme Java renverra l'index normal, à partir de 0. Si la clé n'est pas trouvée, l'algorithme Java renverra l'indice négatif pour la position que la clé aurait occupée (en supposant que le tableau s'étend à droite par un élément).

Package Java et classe pour la recherche binaire

Le schéma de recherche binaire Java fonctionne sur un tableau déjà trié. Les tableaux de classe Java, qui se trouve dans le java.user.* Package, a binarysearch () Méthodes pour la recherche binaire d'un tableau déjà trié. Chacune de ces méthodes renvoie un entier qui est un index normal si la clé est trouvée, ou un indice négatif, comme expliqué ci-dessus, si la clé n'est pas trouvée. Deux de ces méthodes sont destinées aux caractères.

Construire le tableau de recherche

La deuxième liste ci-dessus sera utilisée pour illustrer le codage de recherche binaire en Java. L'instruction suivante peut être utilisée pour construire le tableau trié:

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;

Le schéma de recherche binaire Java fonctionne sur une liste déjà triée.

Méthodes de recherche binaire de la classe des tableaux

Le tableau ci-dessus de Chars sera utilisé dans cette section pour l'illustration. Les méthodes de recherche binaire sont dans la classe des tableaux du java.user.* emballer. Ce package doit être importé pour que la classe des tableaux soit utilisée.

Toutes les méthodes de la classe des tableaux sont des méthodes statiques. Cela signifie qu'un objet n'a pas besoin d'être instancié pour aucune de ses méthodes à utiliser. Deux de ces méthodes sont des méthodes de recherche binaires pour Chars. La syntaxe de l'une des méthodes de recherche binaire, pour les caractères est:

public static int binararysearch (char [] a, char key)

Le programme suivant recherche S qui se trouve:

Importer Java.user.*
classe publique TheClass
public static void main (String [] args)
char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
Int ret = tableaux.BinarySearch (arr, «s»);
Système.dehors.println (ret);

La sortie est 6. Le segment de code suivant recherche B, U et Z qui ne sont pas trouvés.

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret1 = tableaux.BinarySearch (arr, «b»);
int ret2 = tableaux.BinarySearch (arr, «u»);
int ret3 = tableaux.BinarySearch (arr, «z»);
Système.dehors.print (ret1); Système.dehors.imprimer ("); système.dehors.print (ret2);
Système.dehors.imprimer ("); système.dehors.imprimer (ret3); Système.dehors.imprimer(");
Système.dehors.println ();

La sortie est,

-1 -9 -11

Recherche d'une plage

La syntaxe pour rechercher une gamme de caractères est:

public static int binararysearch (char [] a, int fromindex, int toindex, char key)

FromIndex est l'indice normal à lequel la plage commence. Toindex est l'indice normal juste après le dernier élément de la plage. Le segment de code suivant recherche le tableau trié commençant de l'index 3 à l'index 7, qui est l'index 8. L'élément de l'index 8 n'est pas inclus dans la plage.

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
Int ret = tableaux.BinarySearch (arr, 3, 8, «s»);
Système.dehors.println (ret);

La clé est s, et la sortie est 6.

Conclusion

Les syntaxes des tableaux pour la recherche d'un tableau de types primitifs sont:

• public static int binararysearch (octet [] a, key octet)
• public static int binararysearch (byte [] a, int fromindex, int toindex, key octet)
• public static int binararysearch (char [] a, char key)
• public static int binararysearch (char [] a, int fromindex, int toindex, char key)
• public static int binararysearch (double [] a, double clé)
• public static int binararysearch (double [] a, int fromindex, int toindex, double key)
• public static int binararysearch (float [] a, key float)
• public static int binararysearch (float [] a, int fromindex, int toindex, float key)
• public static int binararysearch (int [] a, int key)
• public static int binararysearch (int [] a, int fromindex, int toindex, int key)