M1103 Mini-feuille 6

Exercice 1 — Recherche dans des vecteurs triés

Téléchargez le fichier code.zip et ajoutez son contenu (les fichiers search.cpp, search.h, car.cpp, car.h, test.h, asserts.h) à un nouveau projet Code::Blocks.

Dans cet exercice, nous voulons implémenter différents algorithmes de recherche dans des vecteurs triés.

Les éléments à chercher seront des instances de la classe Car définie dans les fichiers car.h et car.cpp. C’est une version simplifiée de votre classe de la mini-feuille 4. En particulier, une voiture contient seulement sa vitesse maximale et pas d’autres informations. Utilisez les opérateurs de comparaison qui ont été définie pour des instances de la classe Car pour implémenter les algorithmes de recherche.

a — Recherche linéaire

Nous commençons avec une recherche linéaire simple.

Implémenter une recherche linéaire d’une voiture car dans un vecteur vec de voitures en complétant la fonction linear_search dans le fichier search.cpp. Cette fonction doit retourner true si car se trouve dans le vecteur et false sinon.

Vous pouvez tester votre fonction en lançant le programme dont la fonction main est définie dans le fichier test.cpp.

b — Recherche dichotomique

Pour améliorer la complexité en temps de notre recherche, nous allons maintenant utiliser une recherche dichotomique.

Implémenter une recherche dichotomique d’une voiture car dans un vecteur vec de voitures en complétant la fonction binary_search dans le fichier search.cpp. Cette fonction doit retourner true si car se trouve dans le vecteur et false sinon.

Vous pouvez tester votre fonction en lançant le programme dont la fonction main est définie dans le fichier test.cpp.

c — Recherche dichotomique du premier indice

Maintenant nous voulons connaître un indice de l’élément à chercher dans le vecteur. Parce qu’un seul élément peut se trouver plusieurs fois dans un vecteur, un tel indice n’est pas nécessairement unique. Nous allons nous intéresser au plus petit indice dans cette question.

Implémenter une recherche dichotomique d’une voiture car dans un vecteur vec de voitures en complétant la fonction binary_search_min dans le fichier search.cpp. Cette fonction doit retourner le plus petit indice de vec auquel se trouve car, ou -1 si car n’est pas dans le vecteur vec.

Vous pouvez tester votre fonction en lançant le programme dont la fonction main est définie dans le fichier test.cpp.

retour au site web du cours