Problème: Rechercher dans un tableau d’entiers A une valeur VAL entrée au clavier. Afficher la position de VAL si elle se trouve dans le tableau, sinon afficher un message correspondant. La valeur POS qui est utilisée pour mémoriser la position de la valeur dans le tableau, aura la valeur -1 aussi longtemps que VAL n’a pas été trouvée.

Implémenter deux versions:

a) La recherche séquentielle

Comparer successivement les valeurs du tableau avec la valeur donnée.

b) La recherche dichotomique (‘recherche binaire’, ‘binary search’)

Condition: Le tableau A doit être trié

Comparer le nombre recherché à la valeur au milieu du tableau,

– s’il y a égalité ou si le tableau est épuisé, arrêter le traitement avec un message correspondant.

– si la valeur recherchée précède la valeur actuelle du tableau, continuer la recherche dans le demi-tableau à gauche de la position actuelle.

– si la valeur recherchée suit la valeur actuelle du tableau, continuer la recherche dans le demi-tableau à droite de la position actuelle.

Ecrire le programme pour le cas où le tableau A est trié par ordre croissant.

Question: Quel est l’avantage de la recherche dichotomique? Expliquer brièvement.

La correction exercices C/C++ (voir page 2 en bas)