Recherche séquentielle dans un tableau

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

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.

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.

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):

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

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 :

1. La correction : L'algorithme fait-il bien ce qu'il doit dans tous les cas ? N'y a-t-il pas des cas problématiques ?
2. L'algorithme est-il rapide ?

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