Recherche dichotomique
Mettre en œuvre l'algorithme de recherche dichotomique dans un tableau trié. Comparer son efficacité logarithmique avec la recherche séquentielle.
À propos de ce thème
Mettre en œuvre l'algorithme de recherche dichotomique dans un tableau trié. Comparer son efficacité logarithmique avec la recherche séquentielle.
Questions clés
- Pourquoi le tableau doit-il être trié pour utiliser la dichotomie ?
- Comment le nombre d'étapes évolue-t-il avec la taille du tableau ?
- Comment prouver la terminaison avec un variant de boucle ?
Plus dans Algorithmique
Parcours séquentiel et recherche
Écrire des algorithmes pour parcourir un tableau à la recherche d'un élément, d'un extremum ou pour calculer une moyenne.
2 methodologies
Algorithmes de tri
Étudier et implémenter les algorithmes de tri par insertion et par sélection. Analyser leur complexité quadratique et prouver leur terminaison.
2 methodologies
Algorithmes gloutons
Résoudre des problèmes d'optimisation à l'aide d'algorithmes gloutons, en s'appuyant sur l'exemple classique du problème du rendu de monnaie.
2 methodologies