BinaireSearch() en Java

En Java, binaireSearch() est une méthode qui permet de rechercher un élément clé particulier parmi plusieurs éléments à l'aide de l'algorithme de recherche binaire. Pour effectuer cette opération, les éléments doivent être triés par ordre croissant. S'il n'est pas trié, il peut l'être à l'aide de la méthode Arrays.sort(arr). Sinon, les résultats sont dits indéfinis.  Par rapport à la recherche linéaire, la recherche binaire est considérée comme plus rapide. Pour cette raison, la complexité temporelle de la recherche binaire est dite O(log n). De plus, la méthode binaireSearch() peut être instanciée à partir du package java.util.Arrays. Plus de détails sur la méthode binaireSearch() seront abordés dans les sections suivantes.

Syntaxe :

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

public static int binarySearch(Object[] a, Object key)

Ici, les paramètres a et key sont respectivement le tableau à rechercher et la valeur à trouver.

La méthode

binarySearch() renvoie l'index de l'élément clé recherché. Dans le cas où l'élément clé n'est pas trouvé, un point d'insertion où l'élément clé qui aurait été inséré sera renvoyé. Si l'élément clé de la recherche n'est pas comparable aux autres éléments du tableau, une exception appelée ClassCastException sera levée.

Comment fonctionne la méthode BinarySearch() en Java ?

Voyons comment cette méthode fonctionne en Java :

1. Supposons que k soit l'élément clé à rechercher. Comparez k avec l'élément central du tableau.
2. Si k correspond à l'élément en position médiane, l'index médian doit être renvoyé.
3. Sinon, si k est supérieur à l'élément en position médiane, alors k ne peut être trouvé que sur le côté droit de l'élément médian.
4. Sinon, il se trouve sur le côté gauche de l'élément central.

Exemples d'implémentation de BinarySearch() en Java

Vous trouverez ci-dessous des exemples de certains programmes utilisant la méthode BinarySearch().

Exemple n°1

Code :

import java.util.Arrays;
public class BinarySearchExample
{
public static void main(String[] args)
{
//create a byte array
byte ba[] = {05, 10, 15, 20, 25, 30};
//create a character array
char ca[] = {'a', 'n', 's', 'p', 'v', 'i', 'd'};
//create an integer array
int ia[] = { 10, 20, 15, 22, 35};
//create a double array
double da[] = {10.1 , 15.34 , 22.25, 13.5};
//create a float array
float fa[] = {13.2f, 25.1f , 22.2f , 43.5f };
//sort all the arrays that created above
Arrays.sort(ba);
Arrays.sort(ca);
Arrays.sort(ia);
Arrays.sort(da);
Arrays.sort(fa);
//enter the key elements that has to be searched in the array
byte bKey = 15;
char cKey = 'i';
int iKey = 22;
double dKey = 15.34;
float fKey = 22.2f;
System.out.println("Element "+ bKey + " is found at the position of " + Arrays.binarySearch(ba,bKey) );
System.out.println("Element "+ cKey + " is found at the position of " + Arrays.binarySearch(ca,cKey) );
System.out.println("Element "+ iKey + " is found at the position of " + Arrays.binarySearch(ia,iKey) );
System.out.println("Element "+ dKey + " is found at the position of " + Arrays.binarySearch(da,dKey) );
System.out.println("Element "+ fKey + " is found at the position of " + Arrays.binarySearch(fa,fKey) );
}
}

Sortie :

Certains tableaux de différents types tels que caractères, entiers, flottants, doubles et octets sont créés après avoir trié les tableaux à l'aide de Arrays dans la méthode program.Sort() ci-dessus, les éléments qui doivent être recherchés dans les tableaux sont déclarés. Ensuite, l'index de l'élément recherché est imprimé à l'aide de la méthode Arrays.binarySearch().

Supposons qu'un élément clé soit donné et qu'il ne soit pas présent dans le tableau ; quel sera le résultat ??

Pour trouver cela, modifions le code des éléments clés comme indiqué ci-dessous.

octet bKey = 15;
char cKey = 'i';
int iKey = 89;
double dClé = 15,34 ;
float fKey = 22.2f;

C'est-à-dire que iKey=89 n'est pas présent dans le tableau, alors la sortie sera affichée comme ci-dessous.

Comme nous pouvons le voir, la position est imprimée comme -6. En effet, si un élément est recherché et introuvable, la valeur négative de l'index sera renvoyée si cet élément était présent. c'est-à-dire que ,int ia[] = { 10, 20, 15, 22, 35} est le tableau donné. Si 89 étaient présents, le tableau aurait été int ia[] = { 10, 20, 15, 22, 35, 89};

On peut clairement voir que l'index aurait été 6. Comme il n'est pas présent dans le tableau d'origine, la valeur négative de cet index particulier est renvoyée dans la sortie ci-dessus.

Exemple n°2

Une recherche binaire peut également être effectuée à l'aide de la récursivité, comme indiqué ci-dessous.

Code :

//sample class
class BinarySearchExample{
public static int binarySearch(int a[], int f, int l, int k){
//if last element is greater than or equal to first element
if (l>=f)
{
//find the mid
int m = f + (l - f)/2;
//if the key element that is searching is found in middle position, return mid position
if (a[m] == k)
{
return m;
}
//if key element is less than element in middle position, search the left <u>subarray</u>
if (a[m] > k){
return binarySearch(a, f, m-1, k);
}
//if key element is greater than the element in middle position, search the right <u>subarray</u>
else{
return binarySearch(a, m+1, l, k);
}
}
return -1;
}
public static void main(String args[]){
//initialise the array
int a[] = {34,45,54,68,79};
int k = 68;
int l = a.length-1;
//store the position in variable res
int res = binarySearch(a,0,l,k);
if (res == -1)
System.out.println("Sorry!! Can't find the element....!");
else
System.out.println("Element is found at the position: "+res);
}
}

Sortie :

Dans le programme ci-dessus, un tableau est d'abord créé et l'élément à découvrir est également déclaré. Grâce à la méthode binaireSearch(), la position des éléments clés sera découverte.  Supposons que l'élément ne soit pas trouvé, un message sera imprimé comme "Désolé !!! Impossible de trouver l'élément".

Conclusion

binarySearch() est une méthode Java qui permet de trouver un élément clé particulier parmi plusieurs éléments disponibles dans le tableau à l'aide de l'algorithme de recherche binaire. Le fonctionnement et des exemples de cette méthode sont expliqués en détail dans ce document.

Article recommandé

Ceci est un guide de BinarySearch() en Java. Nous discutons ici du fonctionnement de la méthode BinarySearch() en Java et des exemples d'implémentation de code. Vous pouvez également consulter nos autres articles suggérés pour en savoir plus –

1. Fonctions mathématiques JavaScript
2. Mise en page en Java
3. Compilateurs Java
4. Fusionner le tri en Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!