Solution de Recherche dichotomique - Sujet 18 - EP NSI 2025

Exercice 1

EXERCICE 1 (10 points)

Écrire une fonction moyenne qui prend en paramètre un tableau d’entiers non vide et qui renvoie un nombre flottant donnant la moyenne de ces entiers.

Attention : il est interdit d’utiliser la fonction sum ou la fonction mean (module statistics) de Python.

Exemples

>>> moyenne([1])
1.0
>>> moyenne([1, 2, 3, 4, 5, 6, 7])
4.0
>>> moyenne([1, 2])
1.5

Exercice 2

EXERCICE 2 (10 points)

Le but de l’exercice est de compléter une fonction qui détermine si une valeur est présente dans un tableau de valeurs triées dans l’ordre croissant.

Compléter l’algorithme de dichotomie donné ci-après.

def dichotomie(tab, x):
    """applique une recherche dichotomique pour déterminer
    si x est dans le tableau trié tab.
    La fonction renvoie True si tab contient x et False sinon"""

    debut = 0
    fin = ...
    while debut <= fin:
        m = ...
        if x == tab[m]:
            return ...
        if x > tab[m]:
            debut = ...
        else:
            fin = ...
    return False

Exemples :

>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 28)
True
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 27)
False
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33], 1)
False
>>> dichotomie([], 28)
False

Les contraintes ci-dessous sont ajoutées par la plateforme et ne font pas partie du sujet.

Exercice 1

Contraintes :

• tab est une liste d’entiers non vide : 1 <= len(tab) <= 10^5
• -10^9 <= tab[i] <= 10^9
• La valeur renvoyée est un flottant (float), y compris lorsque la moyenne est entière : moyenne([1]) vaut 1.0
• Le tableau vide est hors du domaine de l’exercice 1 et n’est jamais transmis à moyenne

Exercice 2

Contraintes :

• tab est une liste d’entiers triée dans l’ordre croissant, éventuellement vide : 0 <= len(tab) <= 10^5
• -10^9 <= tab[i] <= 10^9 et -10^9 <= x <= 10^9
• Des valeurs égales peuvent apparaître plusieurs fois dans tab
• dichotomie([], x) renvoie False
• La valeur renvoyée est un booléen : True si x est présent dans tab, False sinon
• dichotomie peut être appelée jusqu’à 10^5 fois sur un même tableau : une solution parcourant tab séquentiellement, en O(n) par appel, dépassera la limite de temps

Exercice 1 - la moyenne d’un tableau

L’idée. La moyenne, c’est la somme de toutes les valeurs divisée par leur nombre. Comme sum est interdit, on calcule la somme nous-mêmes : on part de 0, puis on parcourt le tableau en ajoutant chaque valeur au total. À la fin, on divise ce total par len(tab).

Un exemple. Pour [1, 2], la somme vaut 0 + 1 + 2 = 3, il y a 2 valeurs, donc la moyenne est 3 / 2 = 1.5.

def moyenne(tab):
    somme = 0
    for valeur in tab:
        somme = somme + valeur
    # La division / renvoie toujours un flottant, meme quand la moyenne tombe juste
    return somme / len(tab)

somme accumule le total au fur et à mesure du parcours : elle vaut 0 avant la boucle, et contient la somme complète une fois la boucle terminée. L’énoncé garantit que le tableau n’est pas vide, donc len(tab) n’est jamais 0 et la division est toujours possible.

Attention à l’opérateur choisi pour cette division. En Python, / renvoie toujours un flottant, même quand le résultat tombe juste : 7 / 7 vaut 1.0 et non 1. C’est exactement ce que demande l’énoncé. Avec // on obtiendrait un entier, et moyenne([1, 2]) renverrait 1 au lieu de 1.5.

Exercice 2 - la recherche dichotomique

L’idée. Le tableau est trié : c’est ce qui permet d’aller beaucoup plus vite qu’en regardant les cases une par une. On regarde la valeur du milieu. Si c’est celle que l’on cherche, c’est gagné. Sinon, le tri nous dit de quel côté continuer : si x est plus grand que le milieu, il ne peut se trouver que dans la moitié droite, sinon dans la moitié gauche. On recommence sur cette moitié. La zone de recherche étant divisée par deux à chaque tour, elle devient vide très rapidement.

Un exemple. Cherchons 28 dans [15, 16, 18, 19, 23, 24, 28, 29, 31, 33]. La zone va d’abord de l’indice 0 à l’indice 9, son milieu est l’indice 4 qui contient 23 : comme 28 > 23, on garde les indices 5 à 9. Le milieu est alors l’indice 7 qui contient 29 : comme 28 < 29, on garde les indices 5 à 6. Le milieu est l’indice 5 qui contient 24 : on garde l’indice 6, qui contient 28. Trouvé en 4 tours au lieu de 7.

def dichotomie(tab, x):
    """applique une recherche dichotomique pour déterminer
    si x est dans le tableau trié tab.
    La fonction renvoie True si tab contient x et False sinon"""

    debut = 0
    fin = len(tab) - 1
    while debut <= fin:
        m = (debut + fin) // 2
        if x == tab[m]:
            return True
        if x > tab[m]:
            debut = m + 1
        else:
            fin = m - 1
    return False

debut et fin délimitent la zone du tableau où x peut encore se trouver : au départ le tableau entier, donc de 0 à len(tab) - 1. m est l’indice du milieu de cette zone ; on le calcule avec // pour obtenir un entier, seul un entier pouvant servir d’indice.

Quand on écarte une moitié, on écrit m + 1 ou m - 1, et surtout pas m : la case m vient d’être comparée à x et on sait qu’elle est différente, il est donc inutile de la regarder à nouveau. Si on ne l’excluait pas, la zone cesserait de rétrécir et la boucle tournerait indéfiniment.

La boucle s’arrête dès que debut dépasse fin : la zone est alors vide, x ne peut être nulle part, et le return False de la dernière ligne conclut. C’est aussi ce qui règle le cas du tableau vide sans avoir à le traiter à part : fin vaut -1 dès le départ, la condition debut <= fin est fausse immédiatement, et dichotomie([], 28) renvoie bien False.