Méthode «diviser pour régner»

I. Principe de la méthode « Diviser pour régner »⚓︎

On prend un problème (généralement complexe à résoudre), on divise ce problème en une multitude de petits problèmes, l'idée étant que les « petits problèmes » seront plus simples à résoudre que le problème original.
Une fois les petits problèmes résolus, on recombine les « petits problèmes résolus » afin d'obtenir la solution du problème de départ.

La méthode « diviser pour régner » repose donc sur 3 étapes :

DIVISER : le problème d'origine est divisé en un certain nombre de sous-problèmes
RÉGNER : on résout les sous-problèmes (les sous-problèmes sont plus faciles à résoudre que le problème d'origine)
COMBINER : les solutions des sous-problèmes sont combinées afin d'obtenir la solution du problème d'origine.

Les algorithmes du type « diviser pour régner » sont très souvent des algorithmes récursifs.

II. Exemples d'application⚓︎

2.1. Recherche dichotomique⚓︎

La recherche dichotomique, ou recherche par dichotomie (en anglais : binary search), est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié.

Le principe est de comparer l'élément avec la valeur de la case au milieu du tableau :

si les valeurs sont égales, la tâche est accomplie,
sinon on recommence dans la moitié du tableau pertinente.

Implémentations en python

🐍 Editeur

def dichotomie(tab: list[int], v: int) -> bool:
    """
    Fonction itérative de recherche dichotomique de l'entier v dans le tableau
    d'entiers tab trié en ordre croissant renvoyant un booléen selon que v est
    dans tab ou non

    """
    a = 0  # indice du 1er élément de tab
    b = len(tab) - 1  # indice du dernier élément de tab
    while a <= b:
        m = (a + b) // 2  # indice du milieu
        if tab[m] == v:  # valeur trouvée
              return True
        elif tab[m] > v:  # v n'est pas dans la moitié droite de tab
          b = m - 1
        else:
          a = m + 1  # v n'est pas dans la moitié gauche de tab
    return False

▶️ Console

>>> dichotomie([1, 2, 4, 6, 9, 12, 14], 6)
True

>>> dichotomie([1, 2, 4, 6, 9, 12, 14], 5)
False

🐍 Editeur

def dichotomie(tab: list[int], v: int, a: int=0, b: int=None) -> bool:
    """
    Fonction récursive de recherche dichotomique de l'entier v dans le tableau
    d'entiers tab trié en ordre croissant renvoyant un booléen selon que v est
    dans tab ou non

    """
    if b is None:
        b = len(tab) - 1
    if a > b:
        return False
    m = (a + b) // 2  # indice du milieu
    if tab[m] == v:  # valeur trouvée
        return True
    elif tab[m] > v:  # v n'est pas dans la moitié droite de tab
          return dichotomie(tab, v, a, m-1)
    else:  # v n'est pas dans la moitié gauche de tab
        return dichotomie(tab, v, m+1, b)

▶️ Console

>>> dichotomie([1, 2, 4, 6, 9, 12, 14], 6)
True

>>> dichotomie([1, 2, 4, 6, 9, 12, 14], 5)
False

2.2. Tri fusion⚓︎

On a déjà étudié des algorithmes de tri : le tri par insertion et le tri par sélection.
On va maintenant étudier une nouvelle méthode de tri, le tri-fusion. Comme pour les algorithmes déjà étudiés, cet algorithme de tri fusion prend en entrée un tableau non trié et donne en sortie le tableau trié.

Le tri fusion d’un tableau est un algorithme qui consiste à découper le tableau en deux sous-tableaux, à trier chaque sous-tableau, puis à les fusionner.
Ce tri utilise la méthode « diviser pour régner ».