Solution de Recherche séquentielle dans un tableau - Sujet 13 - EP NSI 2025

Exercice 1

Écrire une fonction recherche qui prend en paramètres elt nombre entier et tab un tableau de nombres entiers (type list), et qui renvoie l’indice de la première occurrence de elt dans tab si elt est dans tab et None sinon.

L’objectif de cet exercice est de parcourir un tableau, il est interdit d’utiliser la méthode index des listes Python.

Exemples :

>>> recherche(1, [2, 3, 4]) # renvoie None
>>> recherche(1, [10, 12, 1, 56])
2
>>> recherche(50, [1, 50, 1])
1
>>> recherche(15, [8, 9, 10, 15])
3

Exercice 2

On considère la fonction insere ci-dessous qui prend en argument un tableau tab d’entiers triés par ordre croissant et un entier a. Cette fonction crée et renvoie un nouveau tableau tab d’entiers triés par ordre croissant.

Cette fonction crée et renvoie un nouveau tableau à partir de celui fourni en paramètre en y insérant la valeur a de sorte que le tableau renvoyé soit encore trié par ordre croissant. Les tableaux seront représentés sous la forme de listes Python.

def insere(tab, a):
    """
    Insère l'élément a (int) dans le tableau tab (list)
    trié par ordre croissant à sa place et renvoie le
    nouveau tableau.
    """
    tab_a = [ a ] + tab # nouveau tableau contenant a
                        # suivi des éléments de tab
    i = 0
    while i < ... and a > ...:
        tab_a[i] = ...
        tab_a[i+1] = a
        i = ...
    return tab_a

Compléter la fonction insere ci-dessus.

Exemples :

>>> insere([1, 2, 4, 5], 3)
[1, 2, 3, 4, 5]
>>> insere([1, 2, 7, 12, 14, 25], 30)
[1, 2, 7, 12, 14, 25, 30]
>>> insere([2, 3, 4], 1)
[1, 2, 3, 4]
>>> insere([], 1)
[1]

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

Exercice 1

Contraintes :

• 0 <= len(tab) <= 10^4
• -10^9 <= elt <= 10^9
• -10^9 <= tab[i] <= 10^9
• tab n’est pas nécessairement trié et peut contenir des doublons
• si elt n’apparaît pas dans tab, la fonction renvoie None

Exercice 2

Contraintes :

• 0 <= len(tab) <= 10^4
• -10^9 <= a <= 10^9
• -10^9 <= tab[i] <= 10^9
• tab est trié dans l’ordre croissant et peut contenir des doublons
• le tableau renvoyé est un nouveau tableau de longueur len(tab) + 1, trié dans l’ordre croissant

Exercice 1 - recherche de la première occurrence

L’idée. On n’a pas le droit d’utiliser index, donc on fait le travail nous-mêmes : on regarde les cases du tableau une par une, de la gauche vers la droite. Dès qu’une case contient elt, on renvoie tout de suite son indice. Si on arrive au bout du tableau sans avoir rien trouvé, c’est que elt n’y est pas : on renvoie None.

Comme on parcourt de gauche à droite et qu’on s’arrête au premier succès, l’indice renvoyé est bien celui de la première occurrence.

Un petit exemple. Pour recherche(50, [1, 50, 1]) : la case 0 vaut 1, ce n’est pas 50 ; la case 1 vaut 50, on renvoie 1 et on ne regarde même pas la case 2.

def recherche(elt, tab):
    # On parcourt le tableau du début vers la fin : le premier indice où
    # on trouve elt est donc bien celui de la première occurrence
    for i in range(len(tab)):
        if tab[i] == elt:
            return i
    return None

Explications. i prend successivement toutes les valeurs de 0 à len(tab) - 1, c’est-à-dire tous les indices valides du tableau. Le return i placé dans la boucle fait deux choses à la fois : il donne la réponse et il arrête la fonction, donc la boucle ne continue pas après une occurrence trouvée.

Le return None est en dehors de la boucle, décalé à gauche : on ne l’atteint que si la boucle est allée jusqu’au bout sans jamais entrer dans le if. C’est l’erreur classique sur cet exercice : si on écrit ce return None à l’intérieur de la boucle (par exemple dans un else), la fonction s’arrête dès la première case qui ne convient pas et ne cherche jamais plus loin.

Si tab est vide, range(0) est vide, la boucle ne tourne aucune fois et on renvoie None : le cas du tableau vide se traite tout seul, sans test supplémentaire.

Exercice 2 - insérer une valeur dans un tableau trié

L’idée. Le tableau tab_a du départ contient a en tête, suivi de tous les éléments de tab. Si a est plus petit que tout le reste, c’est déjà fini. Sinon, il faut faire glisser a vers la droite, une case à la fois : à chaque tour, on échange a avec l’élément qui se trouve juste après lui, et on recommence tant que a est plus grand que cet élément.

Un petit exemple. Pour insere([1, 2, 4, 5], 3), on part de [3, 1, 2, 4, 5]. Comme 3 > 1, on échange : [1, 3, 2, 4, 5]. Comme 3 > 2, on échange encore : [1, 2, 3, 4, 5]. Comme 3 > 4 est faux, on s’arrête : a est à sa place.

def insere(tab, a):
    """
    Insère l'élément a (int) dans le tableau tab (list)
    trié par ordre croissant à sa place et renvoie le
    nouveau tableau.
    """
    tab_a = [ a ] + tab # nouveau tableau contenant a
                        # suivi des éléments de tab
    i = 0
    # Tant que a est strictement plus grand que tab[i], on recule tab[i]
    # d'une case vers la gauche et on repose a juste derrière lui
    while i < len(tab) and a > tab[i]:
        tab_a[i] = tab[i]
        tab_a[i+1] = a
        i = i + 1
    return tab_a

Les quatre trous à combler étaient donc len(tab), tab[i], tab[i] et i + 1.

Explications. i compte le nombre d’éléments de tab que a a déjà dépassés ; à chaque tour de boucle, a se trouve dans tab_a à l’indice i. Les deux lignes du corps forment l’échange : on recopie tab[i] à la place que a occupait, puis on repose a juste après, en i+1.

Les deux conditions du while ne sont pas interchangeables. i < len(tab) protège la lecture de tab[i] : sans elle, quand a est plus grand que tous les éléments, on sortirait du tableau. Comme Python évalue le and de gauche à droite et s’arrête dès que la première condition est fausse, tab[i] n’est jamais lu hors des limites. La comparaison a > tab[i] est stricte : si a est égal à tab[i], on s’arrête, et a se place donc avant les valeurs qui lui sont égales - le tableau reste bien trié, doublons compris.

On écrit tab[i] et non tab_a[i] : on compare toujours avec le tableau d’origine, dont les éléments n’ont pas bougé. Enfin, tab lui-même n’est jamais modifié, puisque [ a ] + tab construit une nouvelle liste : la fonction renvoie bien un nouveau tableau, de longueur len(tab) + 1.

Ici aussi, le tableau vide se traite tout seul : pour insere([], 1), la condition i < len(tab) est fausse dès le départ et on renvoie directement [1].