Recherche linéaire et binaire

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Algorithmes de recherche

La recherche est essentielle
- Plusieurs méthodes
Algorithmes pour chercher un élément dans une collection :
- Recherche linéaire
- Recherche binaire

Recherche linéaire

Parcours de chaque élément

Représentation schématique d’une liste de nombres non ordonnés.

Élément trouvé
- l’algorithme s’arrête
- renvoie le résultat
Élément non trouvé
- l’algorithme continue

Recherche linéaire

def linear_search(unordered_list, search_value):

  for index in range(len(unordered_list)):

    if unordered_list[index] == search_value:

      return True

  return False

print(linear_search([15,2,21,3,12,7,8], 8))

True

print(linear_search([15,2,21,3,12,7,8], 800))

False

Recherche linéaire - complexité

Complexité : $O(n)$

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés.

15 ???

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Une variable appelée first pointe vers la première position de la liste.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Une variable appelée first pointe vers la première position de la liste et une autre variable appelée last pointe vers la dernière position.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1


  while first <= last:

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Une variable appelée first pointe vers la première position, une autre appelée last vers la dernière, et une autre appelée middle vers la position du milieu.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

Recherche binaire

S’applique uniquement aux listes ordonnées

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

    if search_value == ordered_list[middle]:

      return True

    elif search_value < ordered_list[middle]:

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Une variable appelée first pointe vers la première position, une autre appelée last vers middle moins un, et une autre appelée middle vers la position du milieu. Les éléments entre first et middle sont en vert.

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1

Recherche binaire

S’applique uniquement aux listes ordonnées

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Une variable appelée first pointe vers middle plus un, une autre appelée last vers la dernière, et une autre appelée middle vers la position du milieu. Les éléments entre first et middle sont en vert.

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Le pointeur middle a bougé et pointe l’élément entre first et last. Les éléments entre first et middle sont en vert.

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Le pointeur middle a bougé et pointe l’élément entre first et last. Les éléments entre first et middle sont en vert. L’élément pointé par middle, 17, va être comparé au nombre 15.

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Le pointeur last a bougé et pointe le même nombre que le pointeur first.

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Le pointeur middle a bougé et pointe le même nombre que les pointeurs first et last.

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Les pointeurs first, last et middle pointent le même nombre, 15, qui va être comparé au nombre 15.

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

Recherche binaire

S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste de nombres ordonnés. Le nombre 15 est encerclé.

15 ???
Comparer search_value avec l’élément du milieu de la liste

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

  return False

Recherche binaire - complexité

Complexité : $O(\log{}n)$

Représentation graphique de la recherche linéaire et de la recherche binaire.

Passons à la pratique !

Structures de données et algorithmes en Python