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




[python] ... [/python] pour insérer un code Python.
[latex] ... [/latex] pour insérer au format latex.

Exemple:

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

[latex]\sqrt{x}[/latex]


Poster un commentaire



Programmes proches

Comparaison entre les tris: Insertion, sélection, à bulles, rapide et fusion
Tri par fusion
Tri Rapide - quicksort -
Tri à bulle
Tri par insertion
Tri par sélection
Recherche dichotomique - Recherche dans une liste triée -
Triangle de Pascal
Les points cols d'une matrice
Transférer un vecteur à une dimension à une matrice à deux dimension
Transférer une matrice à deux dimension en vecteur à une dimension
Produit de deux polynôme
Les listes: Fonctions et méthodes prédéfinies
La puissance d'une matrice carrée
Une matrice neutre d'ordre n
Le produit de deux matrices
Somme de deux matrices
La matrice nulle
Nombre de schtroumpf
Le produit scalaire de deux vecteurs
Insérer un nombre dans une liste triée
Vérifier si une liste est triée
Nombre d'occurrence d'une valeur dans une liste
Chercher une valeur dans une liste non triée (Recherche séquentielle)
Remplir une liste par des zéros à l'aide de compréhension de la liste
La moyenne d'une liste
Le maximum d'une liste
Le minimum d'une liste
Saisir une liste de n valeurs
Taille d'une liste
remplir une liste par des zéros