Implementing Array Algorithms · Implémentation d'algorithmes sur tableaux
| English | Français |
|---|---|
| traversal/træˈvɜːsl/ | traversée |
| index/ˈɪndeks/ | index |
| linear search/ˈlɪnɪə sɜːtʃ/ | recherche linéaire |
Standard array algorithms
- Most array tasks are a traversal 遍历 plus one of a few standard patterns.
- Sum / average: accumulate a total, then divide by
length. - Count: increment when an element matches a condition.
- Min / max: track the smallest or largest seen so far.
Algorithmes standards sur tableau
- La plupart des tâches sur tableau consistent en une traversée 遍历 plus l'un de quelques modèles standards.
- Somme / moyenne : accumuler un total, puis diviser par
length. - Comptage : incrémenter quand un élément correspond à une condition.
- Min / max : suivre la plus petite ou la plus grande valeur rencontrée jusqu'ici.
Finding the maximum
- Start
max = a[0](the first element), then traverse from index1. if (a[i] > max) { max = a[i]; }inside the loop.- After the loop,
maxholds the largest value in the array. - Start from the first element, not
0—0could be larger than every value.
Trouver le maximum
- Commencez par
max = a[0](le premier élément), puis traversez depuis l'indice1. if (a[i] > max) { max = a[i]; }à l'intérieur de la boucle.- Après la boucle,
maxcontient la plus grande valeur du tableau. - Commencez par le premier élément, pas
0—0pourrait être plus grand que toutes les valeurs.
Searching for a value
- To check if a value is present, traverse and compare each element.
- Return the index 下标 where it's found, or
-1if the loop finishes without a match. if (a[i] == target) return i;inside the loop;return -1;after.- This is a linear search 线性查找 (Unit 4.14 covers it in depth).
Rechercher une valeur
- Pour vérifier si une valeur existe, traversez et comparez chaque élément.
- Retournez l'indice 下标 où elle est trouvée, ou
-1si la boucle se termine sans correspondance. if (a[i] == target) return i;à l'intérieur de la boucle ;return -1;à l'extérieur.- C'est une recherche linéaire 线性查找 (Unité 4.14 la couvre en détail).
Shifting and modifying
- Some algorithms move or change elements — e.g. shift everything left, or double each value.
- Modifying needs the indexed loop so you can assign
a[i] = .... - Watch bounds when reading
a[i+1]— the last index has no neighbor. - Trace the indices carefully to avoid an out-of-bounds access.
Décalages et modifications
- Certains algorithmes déplacent ou changent des éléments — par ex. décaler tout vers la gauche, ou doubler chaque valeur.
- Modifier nécessite la boucle indexée pour pouvoir affecter
a[i] = .... - Surveillez les limites lors de la lecture de
a[i+1]— le dernier indice n'a pas de voisin. - Tracez soigneusement les indices pour éviter un accès hors limites.
Initialize a max/min search with the FIRST element, not 0. int max = 0; fails if every value is negative (it would wrongly report 0). Use int max = a[0]; and start the loop at index 1. And when an algorithm reads a[i+1], stop the loop at i < a.length - 1, or the last iteration reads past the end.
Initialisez une recherche min/max avec le PREMIER élément, pas 0. int max = 0; échoue si toutes les valeurs sont négatives (il rapporterait faussement 0). Utilisez int max = a[0]; et commencez la boucle à l'indice 1. Et lorsqu'un algorithme lit a[i+1], arrêtez la boucle à i < a.length - 1, sinon la dernière itération lit au-delà de la fin.
Finding the maximum of a:
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- For
a = {3, 9, 5}: max becomes9.
Trouver le maximum de a :
int max = a[0];for (int i = 1; i < a.length; i++) { if (a[i] > max) max = a[i]; }- Pour
a = {3, 9, 5}: max devient9.
Array algorithms combine a traversal with a pattern: sum/average, count, min/max, or search (return the index or -1). Initialize a min/max with the first element, not 0. Modifying elements needs the indexed loop, and reading a[i+1] needs a tighter bound to stay in range.
Les algorithmes de tableau combinent un parcours avec un motif : somme/moyenne, comptage, min/max, ou recherche (renvoyer l'index ou -1). Initialisez un min/max avec le premier élément, pas 0. La modification des éléments nécessite la boucle indexée, et la lecture de a[i+1] nécessite une borne plus serrée pour rester dans les limites.
Finding the maximum · Trouver le maximum
max starts at a[0]=3, becomes 9, then stays (a = {3,9,5}). · max commence à a[0]=3, devient 9, puis reste (a = {3,9,5}).
To find the maximum of an array, you should initialize max to... · Pour trouver le maximum d'un tableau, vous devriez initialiser max à...
Starting at 0 fails if all values are negative. · Commencer à 0 échoue si toutes les valeurs sont négatives.
For a = {3, 9, 5}, what is the maximum value? · Pour a = {3, 9, 5}, quelle est la valeur maximale ?
9 is the largest element. · 9 est le plus grand élément.
A linear search returns what if the target is not found? · Quel résultat retourne une recherche linéaire si la cible n'est pas trouvée ?
By convention, -1 means 'not found'. · Par convention, -1 signifie « non trouvé ».
An algorithm that reads a[i+1] should loop while... · Un algorithme qui lit a[i+1] doit boucler tant que...
Stopping one early keeps a[i+1] in bounds. · S'arrêter une étape plus tôt garde a[i+1] dans les limites.
Modifying array elements (a[i] = ...) requires the indexed loop, not for-each. · Modifier les éléments du tableau (a[i] = ...) nécessite la boucle indexée, pas for-each.
for-each can't assign back into the array. · for-each ne peut pas écrire en retour dans le tableau.