Recherche par dichotomie

[Soulalex]

<p style="text-align: center;"><span style="font-family:lucida sans unicode,lucida grande,sans-serif;"><span style="font-size: 24px;"><strong>Recherche par dichotomie</strong></span></span></p><p> </p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">La recherche dichotomique est un moyen efficace de trouve l'indice d'un nombre dans un <strong>tableau trié</strong>. Par rapport à une recherche classique, vous ferez moins de lecture dans votre tableau.</span></p><p> </p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;"><span style="font-size: 18px;"><strong>Principe :</strong></span></span></p><hr/><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">C'est très simple !</span></p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">Prenons le tableau contenant 10 éléments : <strong>1 | 4 | 7 | 8 | 10 | 15 | 18 | 19 | 32 | 35</strong></span></p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;"><strong>Celui-ci est trié de manière croissante et il faut qu'il le soit impérativement !</strong></span></p><p> </p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;"><strong>Théorie :</strong></span></p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">Comme dans une recherche simple, vous allez devoir faire une boucle. Mais cette fois <strong>vous commencerez au milieu du tableau</strong> (donc ici à l'indice n°5).</span></p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">Si votre <strong>nombre est inférieur </strong>au nombre de l'indice du milieu (tab[5]), alors<strong> vous vous concentrerez que sur la partie inférieure</strong> (gauche) de votre tableau.</span></p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">Si votre <strong>nombre est supérieur</strong> au nombre de l'indice du milieu (tab[5]), alors<strong> vous vous concentrerez que sur la partie supérieure</strong> (droite) de votre tableau.</span></p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">Vous recommencerez jusqu'à trouver l'indice du nombre.</span></p><p> </p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;"><strong>Exemple :</strong> Je cherche l'indice du nombre 8.</span></p><ol><li><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">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.</span></li><li><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">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.</span></li><li><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">Je me place à la moitié ( (2 + 5) / 2 = 3) . tab[3] = 8 donc je peux arrêter et retourner l'indice correspondant.</span></li></ol><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">En conclusion, je n'ai que 3 itérations avec la recherche dichotomique. Avec une rechercher classique, j'aurais eu 4 itérations. </span></p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">Ceci est peut-être insignifiant dans ce cas mais sur des grands tableaux, la recherche dichotomique est très utile.</span></p><p> </p><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;"><span style="font-size: 18px;"><strong>Implémentation en Java :</strong></span></span></p><hr/><p><span style="font-family:lucida sans unicode,lucida grande,sans-serif;">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 </span></p><p> </p><blockquote class="ipsStyle_spoiler" data-ipsspoiler="" tabindex="0"><pre class="html ipsCode prettyprint" data-pbcklang="html" data-pbcktabsize="4">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;

}</pre><p> </p></blockquote><p> </p>

[vfrz]

<p>Merci pour ce petit cours <img alt=":)" src="emoticons/default_smile.png" title=":)"/></p>