Recherche dichotomique

Algo 07

Résumé du cours

Algorithme de recherche classique

def recherche_classique(tab: list, cherche: int) -> bool:
    for element in tab:
        if element == cherche:
            return True

    # à la fin de la boucle on n'a pas trouvé 'cherche'
    return False
Information

La complexité temporelle de la recherche classique est linéaire.

Algorithme de recherche dichotomique

Les données étant triées, l’algorithme de la dichotomie, pour chercher la présence d’un élément, consiste à:

  • couper le tableau en deux parties égales,
  • ne garder que la partie contenant l’élément,
  • répéter l’opération jusqu’à trouver l’élément ou bien avoir une partie vide.
def recherche_dicho(tab: list, cherche: int) -> bool:
    i_debut = 0
    i_fin = len(tab)-1

    while i_fin >= i_debut:
        i_milieu = (i_debut+i_fin) // 2

        if cherche == tab[i_milieu]:
            return True
        elif cherche < tab[i_milieu]:
            i_fin = i_milieu-1
        else:  # cherche > tab[i_milieu]
            i_debut = i_milieu+1

    # à la fin de la boucle on n'a pas trouvé 'cherche'
    return False
Information

La complexité temporelle de la recherche dichotomique est logarithmique.