GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Recherche séquentielle dans un tableau ======

===== Présentation du problème =====

Imaginons une base de données contenant des entrées comme :

^ Id ^ Nom    ^ Prénom ^ Naissance  ^ Adresse                   ^
| 11 | Dupont | Élia   | 12/04/1997 | 12 rue des Boulets        |
| 25 | Leroy  | Michel | 29/02/1996 | 3 avenue de la République |
| 21 | Aubert | Roland | 31/12/2000 | 11 rue Pirandello         |
| ...| ...    | ...    | ...        | ...                       |

Supposons aussi que l'on veut trouver une ligne avec un //Id// particulier.

Cela revient à **chercher un nombre dans un tableau**.

On ne perd donc rien si on ne considère que la liste de nombres.

===== Recherche d'un nombre dans un tableau de nombres =====

**Exemple :** ''%%[11, 25, 21, ...]%%''

Notre but est, pour un nombre ''needle'' (//needle = aiguille//) donné, de trouver, s'il existe, l'indice de la première occurrence de ''needle'' dans le tableau.

=== Exemple ===

Pour le tableau ''%%[11, 25, 21, 69, 41, 26, 14]%%'',
  * la recherche de ''41'' devrait renvoyer ''4'',
  * la recherche de ''17'' devrait renvoyer, selon le choix que l'on fera, soit ''None'', soit ''-1'', soit ''False'', soit encore une erreur.

Python contient déjà une telle fonction (//testez en console//):

<code python>
>>> tableau = [11, 25, 21, 69, 41, 26, 14]
>>> tableau.index(69)
3
>>> tableau.index(3)
ValueError: 3 is not in list
</code>

===== Question de performances =====

De même qu'il existe diverses façons de trier une liste, plus ou moins performantes, il existe plusieurs façon de chercher un item dans une liste.

Quand on envisage un algorithme, il faut envisager :
  - La [[nsi:premiere:algorithme:correction|correction]] : L'algorithme fait-il bien ce qu'il doit dans tous les cas ? N'y a-t-il pas des cas problématiques ?
  - L'algorithme est-il rapide ?

On va s'intéresser à ces deux aspects.