1NSI : Algorithmique - Parcours Séquentiel d'un Tableau

Problématique

On dispose d'un Tableau d'éléments NON triés (à priori). Un Tableau est une structure de données abstraite an Algorihtmique, pouvant être indexé par un indice entier : en pratique un tableau sera implémenté par une liste en Python.
On souhaite rechercher un élément dans un Tableau, encore une fois NON trié (à priori), par exemple en les parcourant tous un par un (par exemple de gauche à droite ): On parle dans ce cas de parcours séquentiel d'un tableau ou de recherche par balyage.

Remarque Le simple parcours des éléments sans rechercher de valeur particulière peut être également considéré comme un but en soi, mais nous conviendrons que le but de la recherche est de déterminer si OUI, ou NON un élément se trouve dans un Tableau. Eventuellement : Si oui, à quelle place/indice se trouve-t-il?

Tableau NON trié

Si les valeurs ne sont pas triées (voire pire : pas triables), la recherche d'un élément particulier / d'une valeur cible du tableau n'est pas très efficace, au sens de la complexité/coût en temps de l'algorithme.

Exemple : pouvez-vous deviner la couleur à laquelle je pense ?

coul = ["bleu", "jaune", "rouge", "vert", "violet", "marron"]

'Évidence'

• Hormis le test de toutes les valeurs une par une, aucune méthode efficace n'est possible dans un Tableau NON trié.
• Dans une future leçon, nous rechercherons un élément dans une liste triée d'éleménts (par exemples, entiers triés dans l'ordre croissant). On pourra alors tenter d'obtenir un algorithme de recherche plus efficace.

Parcours Séquentiel / Recherche par Balayage

C'est la méthode la plus intuitive : on essaie toutes les valeurs (par exemple, dans l'ordre croissant des indices) jusqu'à trouver la bonne.

Exercice 1

Écrire un code permettant d'afficher l'indice de la valeur 14 dans la liste L = [2, 18, 6, 11, 7, 14, 3, 19, 24].

L = [2, 18, 6, 11, 7, 14, 3, 19, 24]

Corrigé

for k in range(len(L)):
    if L[k] ==  14 :
        return k

Exercice 2

Écrire une fonction trouve(L, p) qui renvoie l'indice d'une valeur p dans une liste L. Si la valeur p n'est pas trouvée, on renverra "non trouvé".

Corrigé

def trouve(L, p) :
    for k in range(len(L)) :
        if L[k] == p :
            return k
    return "non trouvé"

Utilisation

L = ["lundi", "mardi", "mercredi", "jeudi"]

>>> trouve(L,"mardi")
1

>>> trouve(L,"samedi")
'non trouvé'

Complexité de l'Algorithme de Balayage

Le nombre (maximal) d'opérations nécessaires est proportionnel à la taille de la liste à étudier. Si on appelle \(n\) la longueur de la liste, on dit que cet algorithme est d'ordre \(n\), ou linéaire, ou en \(O(n)\).

Questions : - La méthode utilisée nécessitait-elle que la liste soit triée ? - Est-on sûr que cet algorithme s'arrête ?

Peut-on espérer mieux qu'un algorithme en temps linéaire, càd en \(O(n)\), qui vérifie chaque cellule, une par une?