Recherche dichotomique – Recherche dans une liste triée –

Exercice: Recherche dichotomique – Recherche dans une liste triée –

Fonction recherche_dichotomique( v , L) qui retourne l’indice de l’élément recherché v si la valeur v existe dans la liste L, et -1 si v n’existe pas dans la liste L. la valeur v et la liste L sont passés en paramètres.

Une autre technique de recherche dans une liste triée est la recherche dichotomique au lieu de rechercher séquentielle (recherche linière – liste non triée -).

Principe:

On compare la valeur à chercher à la valeur qui se trouve au milieu de la liste.

  • Si c’est le même la valeur donc est trouvée
  • Sinon on recommence soit sur la première moitié si la valeur recherchée est plus petite que la valeur rangé au milieu de la table
  • Soit sur la deuxième moitié si la valeur recherchée est plus grande que la valeur rangé au milieu de la liste.

Exemple d’exécution:

>>> L =[ 2 , 3 , 6 , 12 , 23 , 30 ]
>>> recherche_dichotomique( 6 , L)
2
>>> recherche_dichotomique( 16 , L)
-1

Partager avec...
Share on FacebookShare on Google+Tweet about this on Twitter
Tagués avec : , , , , , , , , , , , , , , , , , ,

Poster un Commentaire

Soyez le premier à commenter !

Utiliser [python] ... [/python] pour insérer un code Python.

$latex format_latex $ pour insérer au format latex.

Exemple:

[python]
print('Hello word')
[/python]

$latex \sqrt{x} $

Laisser un commentaire


Programme similaire