Recherche dichotomique récursive - Sujet 15 - EP NSI 2025

Exercice 1

EXERCICE 1 (10 points)

Programmer la fonction multiplication qui en paramètres deux nombres entiers relatifs n1 et n2, et qui renvoie le produit de ces deux nombres.

Les seules opérations arithmétiques autorisées sont l’addition et la soustraction.

Exemples :

>>> multiplication(3, 5)
15
>>> multiplication(-4, -8)
32
>>> multiplication(-2, 6)
-12
>>> multiplication(-2, 0)
0

Exercice 2

EXERCICE 2 (10 points)

Soit tab un tableau non vide d’entiers triés dans l’ordre croissant et n un entier.

La fonction chercher ci-dessous doit renvoyer un indice où la valeur n apparaît dans tab si cette valeur y figure et None sinon.

Les paramètres de la fonction sont :

tab, le tableau dans lequel s’effectue la recherche ;
x, l’entier à chercher dans le tableau ;
i, l’indice de début de la partie du tableau où s’effectue la recherche ;
j, l’indice de fin de la partie du tableau où s’effectue la recherche.

L’algorithme demandé est une recherche dichotomique récursive.

Recopier et compléter le code de la fonction chercher suivante :

def chercher(tab, x, i, j):
    '''Renvoie l'indice de x dans tab, si x est dans tab, 
    None sinon.
    On suppose que tab est trié dans l'ordre croissant.'''
    if i > j:
        return None
    m = (i + j) // ... 
    if ... < x: 
        return chercher(tab, x, ... , ...) 
    elif tab[m] > x:
        return chercher(tab, x, ... , ...) 
    else:
        return ...

Exemples :

>>> chercher([1, 5, 6, 6, 9, 12], 7, 0, 5)
>>> chercher([1, 5, 6, 6, 9, 12], 9, 0, 5)
4
>>> chercher([1, 5, 6, 6, 9, 12], 6, 0, 5)
2
>>> chercher([1], 0, 0, 0)
>>> chercher([1], 1, 0, 0)
0

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

Exercice 1

Contraintes :

n1 et n2 sont des entiers relatifs
-10^3 <= n1 <= 10^3 et -10^3 <= n2 <= 10^3
la fonction renvoie un entier
seules l’addition et la soustraction sont autorisées comme opérations arithmétiques

Exercice 2

Contraintes :

1 <= len(tab) <= 10^5
tab est un tableau non vide d’entiers triés dans l’ordre croissant, doublons possibles
-10^9 <= tab[k] <= 10^9 et -10^9 <= x <= 10^9
0 <= i < len(tab) et 0 <= j < len(tab) ; l’appel externe se fait avec i = 0 et j = len(tab) - 1
la fonction renvoie None si x ne figure pas dans tab, sinon un indice où la valeur x figure
jusqu’à 2*10^4 appels successifs sont effectués sur un même tableau : une solution en O(len(tab)) par appel dépassera la limite de temps

Énoncé du problème

Exercice 1

Exercice 2