Rechercher dans des listes triées [Quelques algorithmes classiques]

Rechercher dans des listes triées

Objectif

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

Mise en situation

La complexité d'une recherche dans une liste non-triée, à savoir O(n), n'est pas très optimale. En effet, sur de grands volumes de données ou en cas de recherches fréquentes, le temps d'exécution ou les performances pourraient ne pas être au rendez-vous. Pour améliorer cela, le tri préalable de notre liste puis l'utilisation d'un algorithme de recherche dans une liste triée, peuvent grandement améliorer la complexité du problème.

Liste triée

Faire l'hypothèse qu'une liste est triée apporte beaucoup de faciliter à la recherche du développeur. Nous ne traitons ici que des listes triées dans l'ordre croissant seront considérées mais les algorithmes sont pratiquement identiques pour des listes triées dans l'ordre décroissant.

Méthode : Recherche du maximum

L'algorithme dans ce cas est bien plus simple car il suffit d'une seule instruction pour trouver le maximum. La liste étant triée, il s'agit forcément du dernier élément. L'algorithme est donc en O(1) (par rapport au O(n) dans le cas d'une liste non triée).

/** JavaScript : Recherche du maximum dans une liste triée. */
const sortedTemperatures = [-3, 5, 12, 29]
const max = sortedTemperatures[sortedTemperatures.length - 1]
console.log(max)

/** JavaScript : Recherche du maximum dans une liste triée. */
const sortedTemperatures = [-3, 5, 12, 29]

const max = sortedTemperatures[sortedTemperatures.length - 1]

console.log(max)

"""Python : Recherche du maximum dans une liste triée. """
sorted_temperatures = [-3, 5, 12, 29]
max = sorted_temperatures[len(sorted_temperatures)-1]
print(max)

"""Python : Recherche du maximum dans une liste triée. """
sorted_temperatures = [-3, 5, 12, 29]

max = sorted_temperatures[len(sorted_temperatures)-1]

print(max)

Méthode : Recherche naïve des indices d'une valeur

Voici un algorithme naïf qui permet de retourner les indices d'une valeur donnée dans une liste triée. Cet algorithme est dit naïf car il est très intuitif mais n'est pas le plus optimisé dans ce cas.

/** JavaScript : Recherche naïve dans une liste triée. */
const sortedTemperatures = [-3, 5, 12, 50, 50, 78, 94, 113, 129]
const val = 50
let i = 0
while (i < sortedTemperatures.length && sortedTemperatures[i] <= val) {
  if (sortedTemperatures[i] === val) {
    console.log(i)
  }
  i = i + 1
}
console.log('Fin')

/** JavaScript : Recherche naïve dans une liste triée. */
const sortedTemperatures = [-3, 5, 12, 50, 50, 78, 94, 113, 129]
const val = 50
let i = 0
while (i < sortedTemperatures.length && sortedTemperatures[i] <= val) {
  if (sortedTemperatures[i] === val) {
    console.log(i)
  }
  i = i + 1
}
console.log('Fin')

"""Python : Recherche naïve dans une liste triée. """
sorted_temperatures = [-3, 5, 12, 50, 50, 78, 94, 113, 129]
val = 50
i = 0
while (i < len(sorted_temperatures) and sorted_temperatures[i] <= val):
  if sorted_temperatures[i] == val:
    print(i)
  i = i + 1
print("Fin")

"""Python : Recherche naïve dans une liste triée. """
sorted_temperatures = [-3, 5, 12, 50, 50, 78, 94, 113, 129]
val = 50
i = 0
while (i < len(sorted_temperatures) and sorted_temperatures[i] <= val):
  if sorted_temperatures[i] == val:
    print(i)
  i = i + 1
print("Fin")

Exemple : Déroulement pas à pas de la recherche naïve

Pour mieux comprendre cet algorithme, il est intéressant de le faire tourner à la main avec l'exemple sorted_temperatures = [-3, 5, 12, 50, 50, 78, 94, 113, 129] ; val = 50 :

Initialement i = 0 et sorted_temperatures[0] = -3 < 50 donc on entre dans la boucle while.
Première itération: i = 0, sorted_temperatures[0] = -3 est différent de 50 donc la condition if est fausse. On incrémente i pour finir l'itération.
Deuxième itération : i = 1, sorted_temperatures[1] = 5 est différent de 50 donc la condition if est fausse. On incrémente i pour finir l'itération.
Troisième itération : i = 2, sorted_temperatures[2] = 12 est différent de 50 donc la condition if est fausse. On incrémente i pour finir l'itération.
Quatrième itération : i = 3, sorted_temperatures[3] = 50 est égal à 50 donc la condition if est vraie. Le programme affiche i. On incrémente i pour finir l'itération.
Cinquième itération : i = 4, sorted_temperatures[4] = 50 est égal à 50 donc la condition if est vraie. Le programme affiche i. On incrémente i pour finir l'itération.
i = 5 et sorted_temperatures[5] = 78 > 50, la condition while est fausse donc on sort de la boucle et le programme se termine.

Pour résumer, l'affichage du programme sera donc :

3
4
Fin

3
4
Fin

Complément : Recherche de l'indice d'une valeur : dichotomie

Ce problème consiste à renvoie l'indice (le position) d'une valeur donnée, si elle est présente dans une liste. Sachant que la liste est triée, l'algorithme réalise une dichotomie qui permet d'optimiser la recherche. Pour simplifier notre programme, on considère des listes sans doublons (aucune valeur n'est présente deux fois).

L'idée est la suivante : la recherche se fait dans une fenêtre (la liste dans notre cas). La fenêtre initiale est divisée en deux, si l'élément central est plus petit que la valeur, la fenêtre supérieure devient la nouvelle fenêtre de recherche. Sinon c'est la fenêtre inférieure qui le devient. Une fois la nouvelle fenêtre définie, le processus recommence. Ainsi, à chaque itération, la fenêtre de recherche est divisée par deux et l'algorithme converge très vite vers la bonne solution. Dans notre programme, la fenêtre de recherche est définie par les bornes a et b qui sont respectivement les bornes inférieure et supérieure.

/** JavaScript : Dichotomie. */
const sortedTemperatures = [-3, 5, 12, 50, 78, 94, 113, 129]
const val = 50
let a = 0
let b = sortedTemperatures.length - 1
while (a <= b) {
  const m = Math.floor((a + b) / 2)
  if (sortedTemperatures[m] === val) {
    // on a trouvé v
    console.log(m)
    break
  } else if (sortedTemperatures[m] < val) {
    a = m + 1
  } else {
    b = m - 1
  }
}

/** JavaScript : Dichotomie. */
const sortedTemperatures = [-3, 5, 12, 50, 78, 94, 113, 129]
const val = 50

let a = 0
let b = sortedTemperatures.length - 1
while (a <= b) {
  const m = Math.floor((a + b) / 2)
  if (sortedTemperatures[m] === val) {
    // on a trouvé v
    console.log(m)
    break
  } else if (sortedTemperatures[m] < val) {
    a = m + 1
  } else {
    b = m - 1
  }
}

"""Python : Dichotomie. """
sorted_temperatures = [-3, 5, 12, 50, 78, 94, 113, 129]
val = 50
a = 0
b = len(sorted_temperatures) - 1
while a <= b:
  m = (a + b) // 2
  if sorted_temperatures[m] == val:
    # on a trouvé v
    print(m)
    break
  elif sorted_temperatures[m] < val:
    a = m + 1
  else:
    b = m - 1

"""Python : Dichotomie. """
sorted_temperatures = [-3, 5, 12, 50, 78, 94, 113, 129]
val = 50

a = 0
b = len(sorted_temperatures) - 1
while a <= b:
  m = (a + b) // 2
  if sorted_temperatures[m] == val:
    # on a trouvé v
    print(m)
    break
  elif sorted_temperatures[m] < val:
    a = m + 1
  else:
    b = m - 1

Exemple : Déroulement pas à pas de la dichotomie

Pour mieux comprendre cet algorithme, il est intéressant de le faire tourner à la main avec l'exemple sorted_temperatures = [-3, 5, 12, 50, 78, 94, 113, 129] ; val = 50 :

Notre fenêtre est définie avec a = 0 et b = 7
Première itération: m prend la valeur 3 et sorted_temperatures[3]= 50. 50 est supérieur à 12 donc la fenêtre inférieure est conservée, c'est-à-dire b = 2.
Deuxième itération : m prend la valeur 1 et sorted_temperatures[1]= 5. 5 est inférieur à 12 donc la fenêtre supérieure est conservée, c'est-à-dire a = 2.
Troisième itération : m prend la valeur 2 et sorted_temperatures[2]= 12. La valeur a été trouvée, on affiche la position et on sort de la boucle.

Complément : Complexité de ces recherches

La complexité en temps de la dichotomie est O(log(n)). Cette complexité est bien meilleure que O(n) notamment pour des très grandes listes.

À retenir

Une liste triée permet de réduire drastiquement les temps de recherche d'éléments.