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

Énoncé du problème

Exercice 1

Exercice 2