TD3 - Recherche dichotomique

Table des matières

Introduction au TD

La recherche dichotomique est un algorithme très efficace pour retrouver un élément dans un tableau trié. L’idée principale est de réduire l’espace de recherche de moitié à chaque étape, en comparant l’élément recherché avec l’élément du milieu.

Ce TD a pour objectif de :

  • Comprendre le fonctionnement de la recherche dichotomique.
  • Savoir la mettre en œuvre en pseudo-code.
  • Étudier manuellement les étapes et opérations.
  • Identifier le meilleur cas, le pire cas, et le nombre de comparaisons.

Comprendre le principe

Exercice 1

Soit le tableau trié :

T = [2, 4, 7, 10, 15, 20, 25]

On cherche x = 4.

  1. Quelle est la taille du tableau ?
  2. Quel est l’élément du milieu ?
  3. Comparer x avec l’élément du milieu. Quelle partie du tableau devons-nous conserver pour continuer la recherche ?
  4. Répéter jusqu’à trouver l’élément.

Objectif : comprendre visuellement comment la recherche dichotomique réduit l’espace de recherche.

Écrire l'algorithme

Exercice 2

Reprendre le principe expliqué dans le premier exercice et être en mesure de construire l'algorithme de la recherche dichotomique.

  • Précisez les entrées sorties
  • N'oubliez pas de respecter les conventions algorithmique
  • C'est un algorithme récursif !

Simulation et étude des cas

Exercice 3

Pour le tableau :

T = [3, 8, 12, 18, 25, 30, 42, 50]
  1. Chercher x = 25.
  2. Chercher x = 7.

Pour chaque recherche, noter à chaque étape :

  • Valeur de debut, fin, et milieu.
  • Comparaison effectuée.
  • Partie du tableau conservée pour la prochaine étape.

Objectif : visualiser le fonctionnement exact de l’algorithme.

Exercice 4
  1. Pour un tableau de taille $N$, combien de comparaisons au meilleur cas ?
  2. Pour un tableau de taille $N$, combien de comparaisons au pire cas ?
  3. Pourquoi la recherche dichotomique est plus efficace qu’une recherche séquentielle pour de grands tableaux ?
Retour