Tweet
Bonjour, je débute en développement et je suis en ce moment sur les tableaux.Je voudrais bien qu'on m'explique comment écrire un algorithme de tri dichotomique en langage C.
Merci
Merci
-
-
-
Pour commencer, sais tu comment fonctionne la recherche dichotomique ?
La base de la recherche dichotomique est qu'elle s'opère sur un tableau trié.
L'idée est de se placer au centre du tableau et de regarder la valeur que cette case contient.
Si la valeur est inférieur à la valeur cherchée, alors on considérera pour le prochain tour que le début est placé au milieu.
Si la valeur est supérieur alors c'est la fin que l'on placera au milieu.
On retrouve alors le milieu entre le milieu et la fin actuelle et on compare avec la valeur recherchée afin de faire avancer le début ou la fin et ainsi de suite jusqu'à trouver la bonne valeur.
Exemple :
Tableau : 1 3 4 6 8 10
Valeur cherchée 8
On considère que les indices du tableau commencent à 0
D représentera l'indice du début du sous tableau dans lequel on recherche.
F en représentera la fin
Etape 1:
1 3 4 6 8 10
D=0
F=5
La valeur au centre est 6 (élément numéro : 0+(6/2))
La valeur est inférieur à la valeur cherchée donc le début sera placé sur cet élément.
Etape 2:
1 3 4 6 8 10
D=3
F=5
La valeur au milieu est 8 (élément numéro: 3+(3/2))
La valeur correspond à la valeur cherchée --> OK Sinon on continuerai tant que certaines conditions (que je ne dévoilerai pas ici soient remplies ou non).
Voilà la base de l'algo. Je te laisse chercher pour la suite. Pense y en dehors du code avant de le transcrire dans le langage. Cela te facilitera la tâche. Et ne te jettes pas sur la première solution que tu trouves sinon tu n'apprendras pas ou pas bien.
Si tu as des soucis n'hésite pas à demander de l'aide.
Commentaire
Commentaire