|
Complexité : O(n) comparaisons |
|
/* Recherche de la place de x
dans la liste tab de taille longueur */
|
|
| Parcours de la liste entiere | Sortie de boucle dès x trouvé |
| place <== -1 | i <== 0 |
| Répéter pour i allant de 0 à longueur - 1 | Tant que tab[i] <> x ET i< longueur |
| si tab[i] = x | i <== i + 1 |
| alors place <== i | fin_tantque |
| fin_de_répéter | si i >= longueur |
| rendre place | alors rendre -1 |
| sinon rendre i | |
|
Complexité : O(n) comparaisons |
|
/* Recherche de la place du maximum
de la liste tab de taille longueur */
|
| max <== tab[0] |
| place = 0 |
| Répéter pour i allant de 1 à longueur -1 |
| si tab[i] > max |
| alors max <== tab[i] |
|
place <== i |
| fin_de_répéter |
| rendre place |
|
Complexité : O(log(n)) comparaisons |
|
/* Recherche de la place d'insertion
de x dans la liste TRIEE tab de taille longueur */
|
| debut <== 0 |
| fin <== longueur - 1 |
| Répéter |
| med <== (debut + fin)/2 |
| si tab[med] > x |
| alors fin <== med - 1 |
|
sinon debut <== med + 1 |
| tant_que (debut<=fin) |
| rendre debut |
|
Complexité : O(log(n)) comparaisons |
|
/* Recherche de la place de
l'élément x dans la liste TRIEE tab de taille
longueur - Rendre -1 si x n'est pas dans la liste*/
|
| debut <== 0 |
| fin <== longueur - 1 |
| place <== -1 |
| Répéter |
| med <== (debut + fin)/2 |
| si tab[med] = x |
| alors place <== med |
| sinon |
| si tab[med] > x |
| alors fin <== med - 1 |
|
sinon debut <== med + 1 |
| tant_que (debut<=fin) ET (place = -1) |
| rendre place |