Recherche linéaire et recherche binaire

Structures de données et algorithmes en Python

Miriam Antona

Software engineer

Algorithmes de recherche

  • La recherche est essentielle
    • Plusieurs façons
  • Algorithmes pour chercher 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

Schéma 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
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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés.

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

Recherche binaire

  • S'applique seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. Une variable « first » pointe 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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. Une variable « first » pointe la première position de la liste et une autre variable « last » pointe 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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. Une variable « first » pointe la première position, une autre « last » la dernière, et une autre « middle » 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
Structures de données et algorithmes en Python

Recherche binaire

  • S'applique seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. Une variable « first » pointe la première position, une autre « last » la dernière, et une autre « middle » la position du milieu. Le nombre 12 est au milieu et en jaune.

  • 15 ???
  • Comparer 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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. « first » pointe la première position, « last » la position du milieu moins un, et « middle » la position du milieu. Les éléments entre « first » et « middle » sont en vert.

  • 15 ???
  • Comparer 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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. Une variable « first » pointe la première position, une autre « last » la dernière, et une autre « middle » la position du milieu. Le nombre 12 est au milieu et en jaune.

  • 15 ???
  • Comparer 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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. « first » pointe la position du milieu plus un, « last » la dernière, et « middle » la position du milieu. Les éléments entre « first » et « middle » sont en vert.

  • 15 ???
  • Comparer 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 seulement aux listes ordonnées

Schéma 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 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 seulement aux listes ordonnées

Schéma 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, sera comparé au nombre 15.

  • 15 ???
  • Comparer 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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. Le pointeur « last » a bougé et pointe le même nombre que « first ».

  • 15 ???
  • Comparer 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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. Le pointeur « middle » a bougé et pointe le même nombre que « first » et « last ».

  • 15 ???
  • Comparer 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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. Les pointeurs « first », « last » et « middle » pointent le même nombre, 15, qui sera comparé au nombre 15.

  • 15 ???
  • Comparer 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 seulement aux listes ordonnées

Schéma d'une liste de nombres ordonnés. Le nombre 15 est encerclé.

  • 15 ???
  • Comparer 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...