Recherche linéaire et recherche binaire

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Algorithmes de recherche

  • Recherche est une opération essentielle
    • Plusieurs moyens
  • Algorithmes qui recherchent un élément dans une collection :
    • Recherche linéaire
    • Recherche binaire
Structures de données et algorithmes en Python

Recherche linéaire

  • Parcourir chaque élément

Une 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 introuvable
    • l’algorithme continue
Structures de données et algorithmes en Python

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
Structures de données et algorithmes en Python

Recherche linéaire - complexité

  • Complexité : $O(n)$
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

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

  • 15 ???
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

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

  • 15 ???
def binary_search(ordered_list, search_value):
  first = 0
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

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

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


  while first <= last:
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Il existe une variable appelée first qui pointe vers la première position de la liste, une autre variable appelée last qui pointe vers la dernière position, et une autre variable appelée middle qui pointe vers la position centrale.

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

  while first <= last:
    middle = (first + last)//2
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Il existe une variable appelée first qui pointe vers la première position de la liste, une autre variable appelée last qui pointe vers la dernière position, et une autre variable appelée middle qui pointe vers la position centrale. Le nombre 12 est en position centrale et est coloré en jaune.

  • 15 ???
  • Compare search_value avec l’élément au 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]:
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Il existe une variable appelée first qui pointe vers la première position de la liste, une autre variable appelée last qui pointe vers la position du milieu moins un, et une autre variable appelée middle qui pointe vers la position du milieu. Les éléments situés entre les positions première et centrale sont colorés en vert.

  • 15 ???
  • Compare search_value avec l’élément au 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
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Il existe une variable appelée first qui pointe vers la première position de la liste, une autre variable appelée last qui pointe vers la dernière position, et une autre variable appelée middle qui pointe vers la position centrale. Le nombre 12 est en position centrale et est coloré en jaune.

  • 15 ???
  • Compare search_value avec l’élément au 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:
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Il existe une variable appelée first qui pointe vers la position centrale plus un, une autre variable appelée last qui pointe vers la dernière position, et une autre variable appelée middle qui pointe vers la position centrale. Les éléments situés entre les positions initiale et médiane sont colorés en vert.

  • 15 ???
  • Compare search_value avec l’élément au 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
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Le pointeur du milieu a bougé et pointe vers l’élément situé entre le premier et le dernier. Les éléments situés entre les positions première et centrale sont colorés en vert.

  • 15 ???
  • Compare search_value avec l’élément au 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
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Le pointeur du milieu a bougé et pointe vers l’élément situé entre le premier et le dernier. Les éléments situés entre les premières et positions centrales sont colorés en vert. L’élément au point médian, 17, va être comparé au nombre 15.

  • 15 ???
  • Compare search_value avec l’élément au 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
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Le dernier pointeur a été déplacé et pointe vers le même nombre que le premier pointeur.

  • 15 ???
  • Compare search_value avec l’élément au 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
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Le pointeur du milieu a été déplacé et pointe vers le même nombre que les premier et dernier pointeurs.

  • 15 ???
  • Compare search_value avec l’élément au 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
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Les pointeurs du premier, du dernier et du milieu pointent vers le même nombre, 15, qui va être comparé au nombre 15.

  • 15 ???
  • Compare search_value avec l’élément au 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
Structures de données et algorithmes en Python

Recherche binaire

  • S’applique uniquement aux listes ordonnées

Représentation schématique d’une liste contenant des nombres ordonnés. Le nombre 15 est entouré.

  • 15 ???
  • Compare search_value avec l’élément au 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
Structures de données et algorithmes en Python

Recherche binaire - complexité

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

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

Structures de données et algorithmes en Python

Passons à la pratique !

Structures de données et algorithmes en Python

Preparing Video For Download...