Recherche dichotomique - Sujet 10 - EP NSI 2025

Exercice 1

EXERCICE 1 (10 points)

Écrire une fonction recherche qui prend en paramètres un tableau tab de nombres entiers triés par ordre croissant et un nombre entier n, et qui effectue une recherche dichotomique du nombre entier n dans le tableau non vide tab.

Cette fonction doit renvoyer un indice correspondant au nombre cherché s’il est dans le tableau, None sinon.

Exemples :

>>> recherche([2, 3, 4, 5, 6], 5)
3
>>> recherche([2, 3, 4, 6, 7], 5) # renvoie None

Exercice 2

EXERCICE 2 (10 points)

Le codage de César transforme un message en changeant chaque lettre en la décalant dans l’alphabet. Par exemple, avec un décalage de 3, le A se transforme en D, le B en E, …, le X en A, le Y en B et le Z en C. Les autres caractères (‘!’,’ ?’ …) ne sont pas codés.

La fonction position_alphabet ci-dessous prend en paramètre un caractère lettre et renvoie la position de lettre dans la chaîne de caractères alphabet s’il s’y trouve.

La fonction cesar prend en paramètre une chaîne de caractères message et un nombre entier decalage et renvoie le nouveau message codé avec le codage de César utilisant le décalage decalage.

alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def position_alphabet(lettre):
    '''Renvoie la position de la lettre dans l'alphabet'''
    return ord(lettre) - ord('A')

def cesar(message, decalage):
    '''Renvoie le message codé par la méthode de César
    pour le decalage donné'''
    resultat = ''
    for ... in message:
        if 'A' <= c and c <= 'Z':
            indice = (...) % 26
            resultat = resultat + alphabet[indice]
        else:
            resultat = ...
    return resultat

Compléter la fonction cesar.

Exemples :

>>> cesar('BONJOUR A TOUS. VIVE LA MATIERE NSI !', 4)
'FSRNSYV E XSYW. ZMZI PE QEXMIVI RWM !'
>>> cesar('GTSOTZW F YTZX. ANAJ QF RFYNJWJ SXN !', -5)
'BONJOUR A TOUS. VIVE LA MATIERE NSI !'

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

Exercice 1

Contraintes :

1 <= len(tab) <= 10^6 (le tableau tab est non vide)
tab ne contient que des nombres entiers (int) et n est un nombre entier (int)
-10^9 <= tab[i] <= 10^9 et -10^9 <= n <= 10^9
tab est strictement croissant : tab[i] < tab[i+1] pour tout i valide, donc l’indice renvoyé est unique
La fonction renvoie None lorsque n n’appartient pas à tab
Un grand tableau est interrogé par plusieurs milliers de recherches successives : une solution en O(len(tab)) par recherche dépassera la limite de temps

Exercice 2

Contraintes :

0 <= len(message) <= 10^4
message est une chaîne de caractères ASCII imprimables (lettres majuscules et minuscules, chiffres, espaces, ponctuation)
-10^3 <= decalage <= 10^3, decalage peut être négatif ou nul
Seuls les caractères compris entre 'A' et 'Z' sont décalés ; tout autre caractère est recopié tel quel
La chaîne renvoyée a la même longueur que message

Énoncé du problème

Exercice 1

Exercice 2