Pause café #156. Comment utiliser la méthode Arrays.binarySearch() en Java

Source : FreeCodeCamp Avec cet article, vous apprendrez à utiliser la méthode Arrays.binarySearch() en Java.

Qu’est-ce qu’Arrays.binarySearch() en Java ?

La documentation officielle de la méthode Arrays.binarySearch() indique :

• Cette méthode recherche dans le tableau d'octets spécifié la valeur spécifiée à l'aide d'un algorithme de recherche binaire.
• Le tableau doit être trié (à l’aide de la méthode sort(byte[]) ) avant que l’appel ne soit effectué. S'il n'est pas trié, les résultats ne seront pas déterminés.
• Si le tableau contient plusieurs éléments avec la valeur spécifiée, il n'y a aucune garantie lequel sera trouvé.

En termes simples, la méthode Arrays.binarySearch() peut rechercher un élément donné dans un tableau trié et renvoyer son index s'il est trouvé.

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';

		int foundItemIndex = Arrays.binarySearch(vowels, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

La méthode Arrays.binarySearch() prend le tableau que vous souhaitez rechercher comme premier argument et la clé que vous recherchez comme deuxième argument. Le résultat du programme ci-dessus sera : N'oubliez pas que la méthode renvoie l'index de l'élément trouvé, pas l'élément lui-même. De cette façon, vous pouvez stocker l'index sous forme d'entier comme celui utilisé dans cet exemple. Par défaut, la méthode utilise le premier index du tableau comme point de départ de la recherche et la longueur du tableau comme point final de la recherche. Dans ce cas, l'index de début est 0 et l'index de fin est 6. Au lieu d'utiliser les index de début et de fin par défaut, vous pouvez les définir vous-même. Par exemple, si vous souhaitez effectuer une recherche de l'index 2 à l'index 4, vous pouvez procéder comme ceci :

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		int foundItemIndex = Arrays.binarySearch(vowels, startIndex, endIndex, key);

		System.out.println("The given vowel is at index: " + foundItemIndex);

	}
}

Dans ce cas, la méthode Arrays.binarySearch() prend le tableau que vous souhaitez rechercher comme premier argument, l'index de départ comme deuxième argument, l'index de fin comme troisième et la clé comme quatrième. Tant que vous conservez l'index de fin dans la longueur du tableau, la méthode devrait fonctionner correctement. Mais si vous le dépassez, vous obtiendrez une exception Array index out of range . C'est assez simple, non ? La méthode renvoie l'index de l'élément s'il est trouvé. Mais que se passe-t-il s’il ne trouve pas l’élément donné ?

Que se passe-t-il lorsque Arrays.binarySearch() ne trouve pas un élément donné ?

Jetons un autre coup d'œil à la documentation officielle de la méthode Arrays.binarySearch() :

• La méthode trouve l'index d'une clé dans les résultats de la recherche si elle est contenue dans le tableau dans la plage spécifiée ; sinon nous obtenons (-(insertion point) - 1) .
• Le point d'insertion est défini comme le point auquel une clé sera insérée dans le tableau : l'index du premier élément de la plage est supérieur à la clé, ou toIndex (index de fin) si tous les éléments de la plage sont inférieurs à la clé. clé spécifiée.
• Notez que la valeur de retour ne sera supérieure ou égale à 0 que lorsque la clé sera trouvée.

Pas très clair, non ? La première ligne indique que la méthode renverra l'index de la clé issue de la recherche si elle est trouvée dans le tableau. S'il n'est pas trouvé, alors la sortie sera égale à la valeur (-(insertion point) - 1) . Selon la clé de recherche, le point d'insertion peut avoir différentes significations. Disons que nous avons un tableau [5, 6, 7, 8, 9, 10] et une clé de recherche de 0 , qui n'est clairement pas dans le tableau. Dans ce cas, la clé de recherche est inférieure à tous les éléments du tableau. Mais le premier élément supérieur à la clé de recherche est 5 . Ainsi, dans notre cas le point d'insertion sera : Vous pouvez implémenter cela dans un extrait de code comme celui-ci :

package arrays;

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 0)); // -1
	}
}

Supposons à nouveau que nous ayons un tableau [5, 6, 7, 8, 9, 10] et une clé de recherche de 12 , qui n'est clairement pas dans le tableau. Dans ce cas, la clé de recherche est supérieure à tous les éléments du tableau. Ici, le point d'insertion ressemblera à ceci : N'oubliez pas que si vous ne spécifiez pas manuellement l'index de fin, la méthode utilise la longueur du tableau comme index de fin, qui dans ce cas est 6 . Vous pouvez implémenter cela dans un extrait de code comme celui-ci :

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		System.out.println(Arrays.binarySearch(numbers, 12)); // -7
	}
}

Cependant, les résultats changeront si vous définissez manuellement les index de début et de fin :

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int numbers[] = {5, 6, 7, 8, 9, 10};

		int startIndex = 1;
		int endIndex = 3;

		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 5)); // -2
		System.out.println(Arrays.binarySearch(numbers, startIndex, endIndex, 10)); // -4

	}
}

Essayez de calculer les valeurs vous-même. Vous pouvez également utiliser la méthode Arrays.binarySearch() avec des symboles comme celui-ci :

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		char vowels[] = {'a', 'e', 'i', 'o', 'u'};

		char key = 'i';
		int startIndex = 2;
		int endIndex = 4;

		System.out.println(Arrays.binarySearch(vowels, startIndex, endIndex, key));

	}
}

Les mêmes principes s'appliquent si la clé de recherche spécifiée n'est pas trouvée. Mais lors de la comparaison entre un caractère du tableau et une clé de recherche donnée, le code ASCII du caractère correspondant sera utilisé. Autrement dit, A (65) sera inférieur à a (97) . Tenez-en compte lors de la vérification croisée de la sortie de votre programme.