Recherches dans un tableau
Rechercher une valeur
Considérons le tableau suivant : nombres = [8, 7, 2, 10, 3, 1, 6, 5, 9, 4] et cherchons-y la valeur 5.
Contrairement à nous, l'ordinateur n'a pas une vue d'ensemble des valeurs, il ne peut pas immédiatement « voir » le 5 vers la fin du tableau.
Son approche est plus rudimentaire : il passe en revue tous les éléments du tableau jusqu'à trouver le 5 :
Cette méthode est appelée la recherche linéaire ou méthode par balayage.
La fonction lineaire
Compléter la fonction lineaire prenant en argument un tableau et une valeur x et renvoyant l'indice de la première occurrence de x dans tableau.
Si x n'est pas présent dans tableau, la fonction renverra None
Étudions en détails le déroulement de cette fonction en comptant le nombre d'opérations:
- l'algorithme est construit autour d'une boucle « Pour »,
- à chaque itération, la variable
ise voit affecter une nouvelle valeur : \(1\) affectation, - on teste ensuite si
tableau[i]est égal àx: \(1\) accès à la valeur detableau[i]et \(1\) comparaison, - s'il y a égalité on renvoie
i: \(1\) retour, - en fin de boucle on renvoie
None: \(1\) retour.
Remarque
Ce décompte du nombre d'opérations est simpliste. En réalité, Python exécute plus d'opérations.
Si l'on fait le total, on se rend compte que chaque tour de boucle (sans tenir compte du return) nécessite \(3\) opérations. Le return quant à lui, qu'il renvoie un indice ou None rajoute \(1\) opération à l'ensemble.
Dans l'exemple précédent, le 5 cherché était à l'indice 7. Il a donc fallu \(8\) itérations et \(3\times 8 +1=25\) opérations au total.
Compter les opérations ou les itérations
On considère toujours le tableau nombres = [8, 7, 2, 10, 3, 1, 6, 5, 9, 4] et l'on effectue des recherches linéaires.
- La recherche de
8nécessite une seule itération - La recherche de
8nécessite une seule opération - La recherche de
6nécessite \(19\) opérations - La recherche de
4nécessite \(31\) opérations
8est à l'indice0. Il faut donc bien une seule itération
Non car chaque itération nécessite à elle seule \(3\) opérations-
6est à l'indice6. Il faut donc \(7\) itérations et \(3\times 7 + 1= 22\) opérations -
4est à l'indice9. Il faut donc \(10\) itérations et bien \(3\times 10 + 1= 31\) opérations
Le décompte précis des opérations peut être laborieux et très sensible au langage de programmation ou aux instructions saisies pour mettre en œuvre l'algorithme.
Important
Nous allons donc désormais nous contenter de compter les itérations qui ne font que des opérations élémentaires.
Compter les itérations
On a modifié la fonction lineaire afin qu'elle renvoie le nombre d'itérations nécessaires effectuées lors de la recherche de x dans tableau. Cette nouvelle fonction s'appelle lineaire_bis
Si vous exécutez ce code, vous retrouverez le résultat précédent : rechercher 5 nécessite \(8\) itérations.
Modifier x et tableau (si besoin) afin que la recherche de x dans tableau nécessite :
- 1 itération ;
- 2 itérations ;
- 5 itérations dans un tableau de 5 valeurs ;
- 5 itérations dans un tableau de 6 valeurs ;
- 5 itérations dans un tableau contenant 2 fois la valeur cherchée ;
- 6 itérations dans un tableau de 6 valeurs sans que
xne soit présent danstableau.
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
Solution
-
1 itération : Par exemple
lineaire([0], 0) -
2 itérations : Par exemple
lineaire([0, 1], 2) - 5 itérations dans un tableau de 5 valeurs : Par exemple
lineaire([1, 2, 3, 4, 5], 5) - 5 itérations dans un tableau de 6 valeurs : Par exemple
lineaire([1, 2, 3, 4, 5, 6], 5) - 5 itérations dans un tableau contenant 2 fois la valeur cherchée : Par exemple
lineaire([1, 2, 3, 4, 5, 5], 5) - 6 itérations dans un tableau de 6 valeurs sans que
xne soit présent danstableau: Par exemplelineaire([1, 2, 3, 4, 5, 6], 7)
On l'a deviné, l'algorithme effectue un maximum d'itérations dans deux cas de figure :
- soit
xest le dernier élément detableau, - soit
xn'est pas présent danstableau.
Ce sont les deux pires des cas.
Dans chacun d'eux, si le tableau compte \(N\) éléments, il y aura \(N\) itérations. Le nombre d'itérations est égal à la taille du tableau. On dit que l'algorithme de recherche linéaire est de coût linéaire.
Rechercher le minimum
Le tri par sélection nécessite de trouver la valeur minimale du tableau afin de la placer en première position. Ceci fait on recommence à partir de la deuxième position, puis de la troisième, etc.
Nous nous intéressons dans cette partie à la recherche du minimum.
Rechercher le minimum
- Dans le tableau \([3,\,8,\,7,\,1,\,2]\) la recherche du minimum nécessite \(4\) itérations
- Dans le tableau \([1,\,2,\,3,\,4]\) la recherche du minimum nécessite \(4\) itérations
- La recherche du minimum est plus courte s'il est placé au début du tableau
- Dans le tableau \([8,\,8,\,8,\,8]\) la recherche du minimum nécessite \(1\) itération
- Dans le tableau \([3,\,8,\,7,\,1,\,2]\) la recherche du minimum nécessite \(4\) itérations
- Dans le tableau \([1,\,2,\,3,\,4]\) la recherche du minimum nécessite \(4\) itérations
- La recherche du minimum est plus courte s'il est placé au début du tableau
- Dans le tableau \([8,\,8,\,8,\,8]\) la recherche du minimum nécessite \(1\) itération
Il faut lire l'ensemble des valeurs une fois pour être sûr de bien déterminer le minimum. Donc pour un tableau de taille \(N\), il faut faire \(N\) itérations.
On l'a compris, la recherche du minimum nécessite de lire toutes les valeurs une seule fois : le coût est donc linéaire (proportionnel à la taille du tableau).
La fonction indice_du_minimum
Compléter la fonction indice_du_minimum prenant en argument un tableau et renvoyant l'indice de la première occurrence du minimum dans tableau.
On garantit que tableau est non vide.
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)