Manipulation Avancée des Tableaux : Recherche et Algorithmes Simples

Recherche d'un élément dans un tableau

La recherche d'un élément dans un tableau est une opération fréquente. Il existe plusieurs algorithmes de recherche, le plus simple étant la recherche linéaire. La recherche linéaire consiste à parcourir le tableau élément par élément et à comparer chaque élément avec la valeur recherchée. Si la valeur est trouvée, on renvoie son indice ; sinon, on renvoie une valeur spéciale (par exemple, -1) pour indiquer que l'élément n'a pas été trouvé.

Exemple (en Python) :
`def recherche_lineaire(tableau, valeur):`
    `for i in range(len(tableau)):`
        `if tableau[i] == valeur:`
            `return i`
    `return -1`

Complexité : La recherche linéaire a une complexité de O(n) dans le pire des cas, où n est la taille du tableau (on doit parcourir tout le tableau pour trouver l'élément ou constater qu'il n'est pas présent).

Insertion d'un élément dans un tableau

L'insertion d'un élément dans un tableau peut être délicate, surtout si le tableau a une taille fixe. Dans ce cas, il faut souvent créer un nouveau tableau plus grand et copier tous les éléments de l'ancien tableau dans le nouveau, en insérant le nouvel élément à la position souhaitée. Si le tableau est une liste (comme en Python), l'insertion est plus simple grâce à la méthode `insert()` ou `append()` (pour ajouter à la fin).

Exemple (en Python) :
`tableau = [1, 2, 3, 4, 5]`
`tableau.insert(2, 100)` # Insère 100 à l'indice 2
`print(tableau)` # Affiche : [1, 2, 100, 3, 4, 5]

Ajout à la fin :
`tableau.append(6)` # Ajoute 6 à la fin
`print(tableau)` #Affiche [1, 2, 100, 3, 4, 5, 6]

Suppression d'un élément dans un tableau

La suppression d'un élément est similaire à l'insertion. Si le tableau a une taille fixe, il faut créer un nouveau tableau plus petit et copier tous les éléments de l'ancien tableau, en omettant l'élément à supprimer. Avec les listes en Python, on peut utiliser la méthode `remove()` (pour supprimer la première occurrence d'une valeur) ou `pop()` (pour supprimer un élément à un indice donné).

Exemple (en Python) :
`tableau = [1, 2, 3, 4, 5]`
`tableau.remove(3)` # Supprime la première occurrence de la valeur 3
`print(tableau)` # Affiche : [1, 2, 4, 5]

Supprimer par index :
`tableau.pop(1)` # Supprime l'element à l'index 1
`print(tableau)` #Affiche [1, 4, 5]

Algorithmes simples sur les tableaux

Les tableaux sont souvent utilisés pour implémenter des algorithmes simples, tels que :

• Calcul de la somme des éléments : Parcourir le tableau et additionner tous les éléments.
• Calcul de la moyenne : Calculer la somme des éléments et diviser par la taille du tableau.
• Recherche du maximum/minimum : Parcourir le tableau et garder en mémoire l'élément le plus grand/petit rencontré jusqu'à présent.
• Inversion du tableau : Inverser l'ordre des éléments dans le tableau (le premier devient le dernier, le deuxième devient l'avant-dernier, etc.).

Tableaux à plusieurs dimensions

Un tableau à plusieurs dimensions (par exemple, un tableau 2D ou une matrice) est un tableau dont les éléments sont eux-mêmes des tableaux. On peut représenter une matrice comme un tableau de tableaux, où chaque sous-tableau représente une ligne de la matrice. Pour accéder à un élément d'un tableau 2D, on utilise deux indices : l'indice de la ligne et l'indice de la colonne.

Exemple (en Python) :
`matrice = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]`
`print(matrice[0][1])` # Affiche : 2 (élément à la ligne 0, colonne 1)

Ce qu'il faut retenir

• La recherche linéaire permet de trouver un élément dans un tableau en O(n).
• L'insertion et la suppression d'éléments peuvent nécessiter la création d'un nouveau tableau si la taille est fixe. Les listes (en Python) offrent des méthodes pour simplifier ces opérations.
• Les tableaux sont utilisés pour implémenter des algorithmes simples (somme, moyenne, maximum, minimum, inversion).
• Un tableau à plusieurs dimensions est un tableau de tableaux.