Bac recherche dichotomique

Recherche dichotomique → définition ?

C'est un algorithme qui permet de rechercher un élément dans une liste triée en divisant la liste en deux à chaque itération.

Complexité temporelle de la recherche dichotomique ?

La complexité temporelle est $\displaystyle O(log n)$, où $\displaystyle n$ est le nombre d'éléments dans la liste.

Vrai ou Faux : La recherche dichotomique fonctionne sur des listes non triées.

Faux. La recherche dichotomique nécessite que la liste soit triée.

Étapes de la recherche dichotomique ?

1. Déterminer le milieu de la liste. 2. Comparer l'élément central avec l'élément recherché. 3. Réduire la recherche à la moitié appropriée.

Remplir le blanc : La recherche dichotomique nécessite une liste ______.

triée.

Recherche linéaire vs recherche dichotomique.

La recherche linéaire a une complexité de $\displaystyle O(n)$, alors que la recherche dichotomique est $\displaystyle O(log n)$.

Quand utiliser la recherche dichotomique ?

Lorsqu'une liste est triée et que le temps de recherche doit être minimisé.

Vrai ou Faux : La recherche dichotomique peut être implémentée de manière récursive.

Vrai. Elle peut être réalisée avec une approche récursive ou itérative.

Définition de l'élément central ?

C'est l'élément à l'index médian de la liste, utilisé pour comparer avec l'élément recherché.

Cas d'égalité dans la recherche dichotomique ?

Si l'élément central est égal à l'élément recherché, la recherche est terminée avec succès.

À quoi sert l'index de début ?

Il définit la première position de la sous-liste dans laquelle chercher.

À quoi sert l'index de fin ?

Il définit la dernière position de la sous-liste dans laquelle chercher.

Vrai ou Faux : La recherche dichotomique nécessite plus d'espace mémoire que la recherche linéaire.

Faux. La recherche dichotomique utilise moins d'espace mémoire, surtout si elle est implémentée de manière itérative.

Recherche dichotomique itérative vs récursive.

L'itérative utilise une boucle, tandis que la récursive utilise des appels de fonction pour diviser la liste.

Que retourne la recherche dichotomique si l'élément n'est pas trouvé ?

Elle retourne généralement -1 ou une valeur indiquant que l'élément est absent.

La recherche dichotomique est-elle efficace sur de petites listes ?

Non, pour de très petites listes, la recherche linéaire peut être plus rapide en termes de temps d'exécution.

Exemple d'utilisation de la recherche dichotomique ?

Utilisée dans les systèmes de recherche de mots dans des dictionnaires ou bases de données triées.

Que se passe-t-il si la liste est vide ?

La recherche dichotomique ne peut pas être effectuée, et elle devrait retourner une indication d'absence.

Qu'est-ce qu'une liste triée ?

C'est une liste où les éléments sont disposés dans un ordre croissant ou décroissant.

Indexation et recherche dichotomique.

La recherche dichotomique nécessite un accès rapide par index, ce qui est possible dans les tableaux.

Principaux inconvénients de la recherche dichotomique ?

Nécessité de maintenir une liste triée, ce qui peut être coûteux en temps si les éléments changent fréquemment.

Quel type de données peut-on utiliser pour la recherche dichotomique ?

Elle peut être utilisée sur des types de données comparables, comme les entiers, chaînes, etc.

Vrai ou Faux : La recherche dichotomique est simple à implémenter.

Faux. Bien que conceptuellement simple, elle peut être difficile à mettre en œuvre correctement sans erreur.

Un exemple de liste triée ?

[1, 3, 5, 7, 9, 11] est une liste triée croissante.

Comment déterminer la nouvelle plage de recherche ?

Si l'élément recherché est plus petit que l'élément central, on cherche dans la moitié gauche. Sinon, dans la moitié droite.