Recherche dichotomique

Algo 05

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.