Rechercher dans des listes [Quelques algorithmes classiques]

Rechercher dans des listes

Objectif

Savoir rechercher efficacement une valeur dans une liste non triée.

Mise en situation

La recherche de valeurs dans une liste est un des problèmes les plus simples et se présentant très souvent dans le quotidien d'un développeur.

Liste non triée

La recherche dans une liste non triée ne fait aucune hypothèse sur la position des éléments. Par exemple, la valeur maximale peut se trouver n'importe où dans la liste. Ainsi, pour trouver une valeur il faudra toujours parcourir les éléments un à un.

Méthode : Recherche de la position d'une valeur

Ce problème consiste à renvoyer l'indice (la position) d'une valeur donnée si elle est présente dans une liste. Dans ce cas aussi, nous travaillons sur une liste non triée. Il sera nécessaire de parcourir toutes les cases une à une. Le programme ci-dessous renvoie toutes les position de la valeur est celle recherchée. Si elle est présente plusieurs fois, le programme affichera chacun des indices correspondant.

/** JavaScript : cherche une valeur dans une liste de températures. */
const temperatures = [12, 5, 29, -3]
const val = 5 // La valeur à trouver
for (let i = 0; i < temperatures.length; i++) {
  if (val === temperatures[i]) {
    console.log(i)
  }
}

/** JavaScript : cherche une valeur dans une liste de températures. */
const temperatures = [12, 5, 29, -3]
const val = 5 // La valeur à trouver

for (let i = 0; i < temperatures.length; i++) {
  if (val === temperatures[i]) {
    console.log(i)
  }
}

"""Python : cherche une valeur dans une liste de températures. """
temperatures = [12, 5, 29, -3]
val = 5  # Valeur à trouver
for i in range(len(temperatures)):
  if val == temperatures[i]:
    print(i)

"""Python : cherche une valeur dans une liste de températures. """
temperatures = [12, 5, 29, -3]
val = 5  # Valeur à trouver

for i in range(len(temperatures)):
  if val == temperatures[i]:
    print(i)

Méthode : Recherche du maximum

Voici un algorithme qui retourne la valeur maximale d'une liste non triée. L'algorithme teste les éléments un à un et possède une variable qui stocke le maximum.

Cette variable est initialisée avec le premier élément de la liste et est mise à jour dès qu'une valeur plus grande que le maximum actuel est trouvée.

À noter que la recherche du minimum est identique. Il faudra simplement inverser la condition du if à l'intérieur de la boucle..

/** JavaScript : cherche le maximum d'une liste de températures. */
const temperatures = [12, 5, 29, -3]
let max = temperatures[0]
for (let i = 1; i < temperatures.length; i = i + 1) {
  if (max < temperatures[i]) {
    max = temperatures[i]
  }
}
console.log(max)

/** JavaScript : cherche le maximum d'une liste de températures. */
const temperatures = [12, 5, 29, -3]
let max = temperatures[0]
for (let i = 1; i < temperatures.length; i = i + 1) {
  if (max < temperatures[i]) {
    max = temperatures[i]
  }
}

console.log(max)

"""Python : cherche le maximum d'une liste de températures. """
temperatures = [12, 5, 29, -3]
max = temperatures[0]
for i in range(1, len(temperatures)):
  if max < temperatures[i]:
    max = temperatures[i]
print(max)

"""Python : cherche le maximum d'une liste de températures. """
temperatures = [12, 5, 29, -3]
max = temperatures[0]
for i in range(1, len(temperatures)):
  if max < temperatures[i]:
    max = temperatures[i]

print(max)

Exemple : Déroulement pas à pas

Pour mieux comprendre cet algorithme, il est intéressant de le faire tourner à la main avec l'exemple temperatures = [12, 5, 29, -3] :

Avant la boucle : max stocker la valeur 12.
Première itération, i = 1 : max est plus grand que 5 donc l'algorithme passe à l'itération suivante.
Deuxième itération, i = 2 : max est plus petit que 29 donc max prend la valeur 29.
Troisième itération, i = 3 : max est plus grand que -3 donc l'algorithme passe à l'itération suivante.
i = 4 donc la boucle se termine et le programme affiche le résultat, c'est-à-dire 29.

Complément : Complexité de ces recherches

La complexité en temps de ces deux algorithmes est O(n) car il est nécessaire de parcourir tous les éléments de la liste pour trouver ce que l'on cherche.

À retenir

Lorsque l'on cherche un élément dans une liste non-triée, il est nécessaire de parcourir un à un les éléments de celle-ci.