Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Recherche séquentielle dans un tableau

Considérons un tableau T et une valeur needle que l'on souhaite trouver dans le tableau.

L'approche envisagée consiste à parcourir le tableau, dans l'ordre, jusqu'à trouver needle. Quand needle est trouvé, on renvoie l'indice de la première occurrence de needle dans T.

Cette description cache une précondition implicite. Énoncez cette précondition.

Pour éviter cette précondition, on améliore notre notre description :

si needle est dans T, notre fonction renvoie l'indice de la première occurrence,
sinon la fonction renvoie -1

À votre avis, pourquoi préfère-t-on, dans le cas ou needle n'est pas dans T, que la fonction renvoie -1 et pas False ou None ?
Faites l'implémentation de la fonction recherche_sequentielle(T, needle) -> int.

Ajoutez les tests suivants

T = [1, 5, 84, 13, 96, 15, 2, 41, 43, 31, 58, 13, 75, 89]
assert recherche_sequentielle(T, 13) == 3
assert recherche_sequentielle(T, 58) == 10
assert recherche_sequentielle(T, 25) == -1

Évaluation de performances

On se préoccupe du temps approximatif mis par la recherche. Pour évaluer ce temps, on peut considérer que chaque ligne de la fonction s'exécute dans un temps identique attention, ce n'est pas vrai, mais cela suffit ici.

Si le tableau contient $n = 100$ éléments,
- En combien d'instruction se termine la fonction, si on a de la chance ?
- En combien d'instruction se termine la fonction, si on n'a pas de chance ?

On s'intéresse au cas défavorable, quand on n'a pas de chance, c'est à dire ici quand needle n'est pas dans T et que l'on doit parcourir la totalité du tableau.

Combien d'instructions coûte la fonction si le tableau contient 100 éléments ?
Même questions pour 1000, 10000, 100000 éléments ?
En général, pour $n$ éléments ?

On s'intéresse surtout au cas où $n$ est très grand. On peut alors faire des approximations. Par exemple, si $n$ grand, alors $3n+2 \approx 3n$ et $5n^2 + 6n - 1 \approx 5n^2$.

Tenant compte de cette approximations, pour un tableau de $n$ éléments, $n$ grand, quel est le coût de la fonction au pire ?

On ne s'intéresse pas vraiment au coût, mais à l'évolution du coût. C'est à dire : si le tableau devient 2 fois plus grand, comment évolue le coût de la fonction ?

Répondez à cette question.