Recherche par dichotomie

[Soulalex]

Recherche par dichotomie

 

La recherche dichotomique est un moyen efficace de trouve l'indice d'un nombre dans un tableau trié. Par rapport à une recherche classique, vous ferez moins de lecture dans votre tableau.

 

Principe :

---

C'est très simple !

Prenons le tableau contenant 10 éléments : 1 | 4 | 7 | 8 | 10 | 15 | 18 | 19 | 32 | 35

Celui-ci est trié de manière croissante et il faut qu'il le soit impérativement !

 

Théorie :

Comme dans une recherche simple, vous allez devoir faire une boucle. Mais cette fois vous commencerez au milieu du tableau (donc ici à l'indice n°5).

Si votre nombre est inférieur au nombre de l'indice du milieu (tab[5]), alors vous vous concentrerez que sur la partie inférieure (gauche) de votre tableau.

Si votre nombre est supérieur au nombre de l'indice du milieu (tab[5]), alors vous vous concentrerez que sur la partie supérieure (droite) de votre tableau.

Vous recommencerez jusqu'à trouver l'indice du nombre.

 

Exemple : Je cherche l'indice du nombre 8.

1. Je me place à la moitié de mon tableau (indiceMilieu = 5) et je regarde si mon nombre est plus grand, plus petit ou égal. Il est plus petit donc je me concentre sur les nombres d'indices compris entre 0 et 5.
2. Je me place à la moitié ( (0 + 5) / 2 = 2). tab[2] < 8 donc je concentre sur les nombres d'indices compris entre 2 et 5.
3. Je me place à la moitié ( (2 + 5) / 2 = 3) . tab[3] = 8 donc je peux arrêter et retourner l'indice correspondant.

En conclusion, je n'ai que 3 itérations avec la recherche dichotomique. Avec une rechercher classique, j'aurais eu 4 itérations.

Ceci est peut-être insignifiant dans ce cas mais sur des grands tableaux, la recherche dichotomique est très utile.

 

Implémentation en Java :

---

Petit cadeau, je vous offre la fonction java qui permet de faire une recherche par dichotomie mais je vous conseil de la coder vous même car elle n'est pas très dure et c'est toujours instructif de faire les chose sois-même

 

public static int rechercherDichotomie(int[] tab, int nb)
{
    int indMin, indMax, indMid;

    // Si votre tableau n'est pas trié, triez le avant !

    // On prend l'ensemble du tableau au départ
    indMin = 0;
    indMax = tab.length;

    while ((indMax - indMin) > 1)
    {
    	// On prend le milieu entre indMin et indMax
        indMid = ((indMin + indMax) / 2);

        // On détermine si le nombre est supérieur, inférieur ou égal à tab[indMid]
        if (nb > this.tab[indMid]) {
        	indMin = indMid;
        } else if (nb < this.tab[indMid]) {
        	indMax = indMid;
        } else {
        	return indMid;
        }
    }

    // Retourne -1 si l'indice n'a pas été trouvé
    return -1;
}

 

 

[vfrz]

Merci pour ce petit cours