Recherche binaire en Java  Exemple d'algorithme

Article original : Binary Search in Java – Algorithm Example

Les algorithmes fournissent des instructions 00e9tape par 00e9tape pour r00e9soudre des probl00e8mes sp00e9cifiques. Ils vous aident 00e0 r00e9soudre des probl00e8mes en utilisant des 00e9tapes efficaces, standard et r00e9utilisables.

L'algorithme de recherche binaire est l'un des algorithmes couramment utilis00e9s en programmation. Il est utilis00e9 pour rechercher et trouver un 00e9l00e9ment dans un tableau tri00e9.

L'algorithme de recherche binaire est diff00e9rent de l'arbre de recherche binaire (https://www.freecodecamp.org/news/binary-search-tree-traversal-inorder-preorder-post-order-for-bst/). Nous parlerons de leurs diff00e9rences plus tard dans cet article.

Dans cet article, vous apprendrez comment fonctionne l'algorithme de recherche binaire 00e0 l'aide de diagrammes et d'exemples de code.

Vous verrez comment impl00e9menter l'algorithme dans votre programme Java.

Comment fonctionne l'algorithme de recherche binaire ?

Dans cette section, vous verrez une application pratique de la recherche binaire 00e0 l'aide de diagrammes.

L'algorithme de recherche binaire est un algorithme de type "diviser pour r00e9gner" qui recherche un 00e9l00e9ment sp00e9cifique dans un tableau tri00e9.

Notez que la collection d'00e9l00e9ments/tableau doit 00eatre tri00e9e pour que l'algorithme fonctionne efficacement.

Voici les 00e9tapes impliqu00e9es dans l'algorithme de recherche binaire :

00c9tape #1 - Trier le tableau

Pour commencer la recherche, vous devez avoir un tableau tri00e9. L'image ci-dessus montre une collection de nombres tri00e9s dans l'ordre croissant : 2,3,6,8,9,13,20.

Supposons que l'00e9l00e9ment que nous cherchons est 13. Nous allons le stocker dans une variable appel00e9e number_to_search_for.

00c9tape #2 - Choisir les valeurs Low et High

tableau tri00e9 avec les pointeurs low et high

Le premier index du tableau sera d00e9sign00e9 par low tandis que le dernier index sera d00e9sign00e9 par high.

Ces valeurs vous aideront 00e0 obtenir le midpoint du tableau.

Midpoint = (low + high) / 2.

00c9tape #3 - Choisir le Midpoint/00c9l00e9ment du milieu

tableau tri00e9 avec les pointeurs low, high et middle

L'image ci-dessus montre le midpoint qui se trouve au centre du tableau.

Maintenant que vous connaissez le low, le high et le midpoint du tableau, l'op00e9ration de recherche binaire peut commencer.

00c9tape #4 - Recherche binaire

Voici ce qui se passe pendant la recherche binaire :

1. Si number_to_search_for est 00e9gal 00e0 midpoint, l'index du midpoint sera retourn00e9.
2. Si number_to_search_for est plus grand que midpoint, recherchez parmi les 00e9l00e9ments du c00f4t00e9 droit du midpoint.
3. Si number_to_search_for est plus petit que midpoint, recherchez parmi les 00e9l00e9ments du c00f4t00e9 gauche du midpoint.

L'00e9tape 3 ne sera pertinente que si l'00e9tape 2 est fausse. Si number_to_search_for n'existe pas dans le tableau, retournez -1.

Simplifions les 00e9tapes ci-dessus 00e0 l'aide de diagrammes :

Voici le tableau avec lequel nous travaillons : 2,3,6,8,9,13,20.

number_to_search_for = 13.

midpoint = 8.

low = 2.

high = 20.

It00e9ration #1

D'apr00e8s les 00e9tapes 00e9num00e9r00e9es ci-dessus, vous commencez par comparer number_to_search_for 00e0 midpoint.

tableau tri00e9 avec les pointeurs low, high et middle

Comme vous pouvez le voir dans le diagramme ci-dessus, la valeur de number_to_search_for et midpoint ne sont pas les m00eames.

L'00e9tape suivante consiste 00e0 d00e9terminer si number_to_search_for est plus grand ou plus petit que midpoint.

Dans notre cas, il est plus grand que midpoint, donc nous allons nous concentrer sur les 00e9l00e9ments du c00f4t00e9 droit du midpoint  9, 13 et 20.

Cela rend la recherche beaucoup plus rapide car nous avons 00e9limin00e9 la moiti00e9 du tableau qui n'est pas n00e9cessaire.

Nous allons r00e9p00e9ter toutes les 00e9tapes pour ces 00e9l00e9ments 00e9galement.

Les 00e9tapes s'ex00e9cuteront en continu jusqu'00e0 ce que l'00e9l00e9ment soit trouv00e9. Dans le cas o00f9 l'00e9l00e9ment n'existe pas, -1 sera retourn00e9.

It00e9ration #2

tableau tri00e9 avec les pointeurs low, high et middle

En comparant le midpoint et number_to_search_for dans le diagramme ci-dessus, nous avons la m00eame valeur.

00c0 ce stade, l'op00e9ration de recherche binaire s'arr00eate car nous avons trouv00e9 le nombre. L'index du nombre sera retourn00e9.

C'est-00e0-dire : index 5 du tableau original (2,3,6,8,9,13,20).

Dans la section suivante, vous verrez comment impl00e9menter l'algorithme en Java.

Exemple d'algorithme de recherche binaire en Java

class BinarySearch {
    private static int binarySearch(int numArray[], int number_to_search_for) {
        int low = 0;
        int high = numArray.length - 1;

        while (low <= high){
            int middleIndex = (low + high) / 2;
            int middleIndexNumber = numArray[middleIndex];

            if (number_to_search_for == middleIndexNumber){
                return middleIndex;
            }
            if (number_to_search_for < middleIndexNumber){
                high = middleIndex - 1;
            }
            if (number_to_search_for > middleIndexNumber){
                low = middleIndex + 1;
            }
        }

        return -1;
  }
    public static void main(String args[]) {

        int[] arrayofnums = {2,3,6,8,9,13,20};

        System.out.println(binarySearch(arrayofnums, 13));
        // 5

    }

}

Dans le code ci-dessus, nous avons cr00e900e9 une m00e9thode appel00e9e binarySearch avec deux param00e8tres  int numArray[] et int number_to_search_for :

private static int binarySearch(int numArray[], int number_to_search_for){...}

Le premier param00e8tre repr00e9sente le tableau 00e0 parcourir. Le deuxi00e8me repr00e9sente le nombre 00e0 rechercher.

Ensuite, nous avons d00e9fini les variables low et high pour repr00e9senter le premier et le dernier index du tableau :

int low = 0;
int high = numArray.length - 1;

Apr00e8s cela, nous avons cr00e900e9 une boucle while avec des instructions if correspondant aux 3 00e9tapes utilis00e9es dans la section pr00e9c00e9dente (Section #4 - Recherche binaire) :

while (low <= high){
    int middleIndex = (low + high) / 2;
    int middleIndexNumber = numArray[middleIndex];

    if (number_to_search_for == middleIndexNumber){
        return middleIndex;
    }
    if (number_to_search_for < middleIndexNumber){
        high = middleIndex - 1;
    }
    if (number_to_search_for > middleIndexNumber){
        low = middleIndex + 1;
    }
}

Vous pouvez consulter la section 00c9tape #4 - Recherche binaire pour comprendre le code dans la boucle while.

Nous avons ensuite retourn00e9 -1 apr00e8s la boucle while au cas o00f9 le nombre recherch00e9 n'existe pas dans le tableau.

Enfin, nous avons test00e9 la m00e9thode pour nous assurer que la fonctionnalit00e9 fonctionnait comme pr00e9vu :

public static void main(String args[]) {

     int[] arrayofnums = {2,3,6,8,9,13,20};

     System.out.println(binarySearch(arrayofnums, 13));
     // 5

}

Nous avons sp00e9cifi00e9 13 comme deuxi00e8me param00e8tre et obtenu l'index 5 retourn00e9.

Si vous utilisez un nombre qui n'existe pas dans le tableau, vous obtiendrez -1 retourn00e9.

Diff00e9rences entre l'algorithme de recherche binaire et l'arbre de recherche binaire

Bien que l'algorithme de recherche binaire et l'arbre de recherche binaire soient tous deux utilis00e9s pour la recherche, il existe certaines diff00e9rences dans le mode de fonctionnement et la structure de donn00e9es.

Voici quelques diff00e9rences :

• L'algorithme de recherche binaire est utilis00e9 pour la recherche tandis que l'arbre de recherche binaire est utilis00e9 pour la recherche, l'insertion et la suppression.
• L'algorithme de recherche binaire compare l'00e9l00e9ment du milieu avec l'00e9l00e9ment recherch00e9 tandis que l'arbre de recherche binaire compare la valeur des n00f5uds dans un arbre.
• L'algorithme de recherche binaire recherche dans un tableau ou une liste tandis que l'arbre de recherche binaire parcourt un arbre de n00f5uds.

Vous pouvez lire plus sur l'arbre de recherche binaire ici.

R00e9sum00e9

Dans cet article, nous avons parl00e9 de l'algorithme de recherche binaire. Il sert 00e0 rechercher des 00e9l00e9ments sp00e9cifiques dans un tableau.

Nous avons vu comment l'algorithme fonctionne en utilisant des guides visuels. Ensuite, nous avons vu une impl00e9mentation de l'algorithme en Java.

Enfin, nous avons vu les diff00e9rences entre l'algorithme de recherche binaire et l'arbre de recherche binaire.

Bon codage !