====== 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''.

<WRAP box>
Cette description cache une précondition implicite. Énoncez cette précondition.
</WRAP>

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

<WRAP box>
  * À 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 <code python>
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
</code>
</WRAP>

==== É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 <wrap important>attention, ce n'est pas vrai, mais cela suffit ici.</wrap>

<WRAP box>
  * 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 ?
</WRAP>

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.

<WRAP box>
  * 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 ?
</WRAP>

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$.

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

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 ?

<WRAP box>
Répondez à cette question.
</WRAP>