Objectif : effectuer une recherche séquentielle dans un tableau linéaire (une dimension)  non trié et une recherche séquentielle dans un tableau linéaire déjà trié.
 

• Tableau non trié
• Tableau trié

---

TABLEAU NON TRIE

Spécifications de l’algorithme :
 

• Soit t un tableau d'entiers de 1..n éléments non rangés.

 
• On recherche le rang (la place) de l'élément Elt dans ce tableau. L'algorithme renvoie le rang (la valeur -1 est renvoyée lorsque l'élément Elt n'est pas présent dans le tableau t)

Version Tantque avec "et alors" (opérateur et optimisé)

i ¬  1 ;         Tantque (i £ n) et alors (t[i] ¹ Elt) faire                 i ¬  i+1         finTant;         si  i £ n  alors rang ¬  i         sinon rang ¬  -1         Fsi

Version Tantque avec "et" (opérateur et non optimisé)

i ¬  1 ;         Tantque (i < n) et (t[i] ¹ Elt) faire                 i ¬  i+1         finTant;         si  t[i] = Elt alors rang ¬  i         sinon rang ¬  -1         Fsi

Version Tantque avec sentinelle en fin de tableau (rajout d'une cellule)

t[n+1] ¬ Elt ; // sentinelle rajoutée         i ¬  1 ;         Tantque (i £ n) et alors (t[i] ¹ Elt) faire                 i ¬  i+1         finTant;         si  i £ n  alors rang ¬  i         sinon rang ¬  -1         Fsi

Version Pour avec instruction de sortie (Sortirsi)

pour i ¬ 1 jusquà n faire            Sortirsi t[i] = Elt          fpour;         si  i £ n  alors rang ¬  i         sinon rang ¬  -1         Fsi

Proposition de squelette de classe Java à implanter :
 

Remonter 

---

TABLEAU DEJA TRIE

Spécifications de l’algorithme :
 

• Soit t un tableau d'entiers de 1..n éléments rangés par ordre croissant par exemple.

 
• On recherche le rang (la place) de l'élément Elt dans ce tableau. L'algorithme renvoie le rang (la valeur -1 est renvoyée lorsque l'élément Elt n'est pas présent dans le tableau t)

On peut reprendre sans changement les algorithmes précédents travaillant sur un tableau non trié.

On peut aussi utiliser le fait que le dernier élément du tableau est le plus grand élément et s'en servir comme une sorte de sentinelle. Ci-dessous deux versions utilisant cette dernière remarque.

Version Tantque

si t[n] < Elt alors rang ¬  -1     sinon         i ¬  1 ;        Tantque t[i] < Elt faire                 i ¬  i+1         finTant;         rang ¬  i      Fsi

Version pour

si t[n] < Elt alors rang ¬  -1     sinon        pour i ¬ 1 jusquà n-1 faire            Sortirsi t[i] = Elt          fpour;         rang ¬  i      Fsi

Proposition de squelette de classe Java à implanter :
 

Ecrire chacune des méthodes associées à ces algorithmes (prendre soin d'avoir trié le tableau auparavant) exemple de méthode main :

Remonter