Programmation python

Important

L'algorithme de dichotomie et sa traduction en python (version de l'exercice 2) sont à connaître parfaitement.

Première traduction python

• Proposer un code possible traduisant le principe exposé.

def milieu(i, j):
    """
    i -- entier
    j -- entier

    renvoie le milieu entier de [i,j]
    """
    return (i+j)//2


def dichotomie(valeur, tab):
    """
    tab -- liste d'entiers, triée en ordre croissant
    valeur -- entier

    renvoie True si valeur est dans tab, False sinon.
    La recherche est faite suivant le principe de dichotomie:
        - soit valeur == tab[milieu] et c'est fini 
        - soit valeur < tab[milieu]:
            on cherche dans les éléments à gauche de l'élément d'indice milieu
        - soit valeur > tab[milieu]:
            on cherche dans les éléments à droite de l'élément d'indice milieu
    """

Pour simplifier cette première version, on pourra créer à chaque étape une nouvelle liste (limitée aux éléments d'indices avant milieu ou aux éléments d'indices après milieu, suivant les cas).

Un code possible

Dans cette première version, on traduit le principe en créant à chaque étape une "moitié" de liste gauche ou droite dans laquelle limiter la recherche.

def milieu(i, j):
    """
    i -- entier
    j -- entier

    renvoie le milieu entier de [i,j]
    """
    return (i+j)//2


def dichotomie(valeur, tab):
    """
    tab -- liste d'entiers, triée en ordre croissant
    valeur -- entier

    renvoie True si valeur est dans tab, False sinon.
    La recherche est faite suivant le principe de dichotomie.
    """
    copie = [x for x in tab]
    while copie != []:
        centre = milieu(0, len(copie)-1)
        if copie[centre] == valeur: return True
        if copie[centre] < valeur:
            copie = [copie[k] for k in range(centre+1, len(copie))]
        else:
            copie = [copie[k] for k in range(0, centre)]
    return False

# TESTS
from random import randint
L = [randint(-10, 10) for i in range(12, 29)]
L.sort()  
print(dichotomie(8, L))
# vérif avec in:
print(8 in L)

Illustration

Dans ce fichier ipynb, on a modifié la fonction ci-dessus pour ajouter des affichages des étapes intermédiaires.

Exécutez cette version sur quelques exemples pour bien saisir le fonctionnement.

Version html statique:

S'interdire la création de nouvelles listes

Chercher maintenant à écrire une version où l'on ne définit pas de nouvelle liste: la limitation de la zone de recherche sera faite uniquement à l'aide d'indices marquant le début et la fin de la sous-liste dans laquelle chercher.

Un code possible

def milieu(i, j):
    """
    i -- entier
    j -- entier

    renvoie le milieu entier de [i,j]
    """
    return (i+j)//2


def dichotomie(valeur, tab):
    """
    tab -- liste d'entiers, triée en ordre croissant
    valeur -- entier

    renvoie True si valeur est dans tab, False sinon.
    La recherche est faite suivant le principe de dichotomie.
    """

    # principe: on cherche valeur entre tab[gauche] et tab[droite]
    gauche, droite = 0, len(tab)-1

    while gauche <= droite:
        # invariant: 
        # les éléments tab[0], tab[1], ..., tab[gauche-1] sont  < valeur
        # les éléments tab[droite+1], ..., tab[len(tab)-1] sont  > valeur
        # l'indice de valeur, si présent, est donc entre gauche et droite
        centre = milieu(gauche, droite)
        if tab[centre] == valeur: return True
        if tab[centre] < valeur:
            gauche, droite = centre+1, droite
        else:
            gauche, droite = gauche, centre-1


    return False


# TESTS
from random import randint
L = [randint(-10, 10) for i in range(12, 29)]
L.sort()  
print( dichotomie(8, L) )
# vérif avec in:
print( 8 in L )

• Quel peut-être l'intérêt de la version 2 ci-dessus (version sans création de listes intermédiaires) par rapport à la première version ?

Solution

Le principe utilisé est le même. Mais la version créant des listes est plus couteuse en temps et en espace.

• La création d'une liste prend du temps et augmente ici considérablement la complexité (c'est à dire le temps de calcul).
• La création d'une liste prend également de l'espace.

Pour bien comprendre ces deux remarques, imaginez que la liste manipulée ne soit pas une liste d'entiers mais une liste d'objets (que l'on puisse trier) occupant eux-mêmes un nombre important d'octets. Chaque copie d'éléments de la liste (pour créer les listes intermédiaires) prendra alors du temps et la liste copie prendra également de la mémoire supplémentaire.
Le temps supplémentaire pour la version 1 peut donc être considérable.

Renvoyer l'indice d'une occurrence de valeur

Reprendre le code précédent et le modifier pour que la fonction dichotomie:

• renvoie un indice d'une occurrence de valeur dans le cas où valeur est présent
• et renvoie None si valeur n'est pas présent.

Code

def milieu(i, j):
    """
    i -- entier
    j -- entier

    renvoie le milieu entier de [i,j]
    """
    return (i+j)//2


def dichotomie(valeur, tab):
    """
    tab -- liste d'entiers, triée en ordre croissant
    valeur -- entier

    renvoie True si valeur est dans tab, False sinon.
    La recherche est faite suivant le principe de dichotomie.
    """
    gauche, droite = 0, len(tab)-1

    while gauche <= droite:
        centre = milieu(gauche, droite)
        if tab[centre] == valeur: return centre
        if tab[centre] < valeur:
            gauche, droite = centre+1, droite
        else:
            gauche, droite = gauche, centre-1

    return None



# TESTS
from random import randint
L = [randint(-10, 10) for i in range(10)]
L.sort()  
print(L)
print(dichotomie(8, L))