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

Énoncé du problème

Exercice 1

Exercice 2