Recherche linéaire

Algorithme
Recherche linéaire dans une table

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 C# à implanter :

class ApplicationRechLin {
   static void AfficherTable ( int[] table )
   {
             // Affichage du tableau
    }
    static void InitTable ( )
   {
                 // remplissage du tableau
    }
   static int RechSeq1( int[] t, int Elt )
    {
        // Version Tantque avec "et alors" (opérateur et optimisé)
     }
static int RechSeq2( int[] t, int Elt )
{
        // Version Tantque avec "et" (opérateur non optimisé)
}
   static int RechSeq3( int[] t, int Elt )
   {
       // Version Tantque avec sentinelle en fin de tableau
   }
static int RechSeq4( int[] t, int Elt )
{
      // Version Pour avec instruction de sortie break
}
static void Main(string[ ] args)
{
         InitTable ( );
         System.Console.WriteLine("Tableau initial :");
         AfficherTable (table );
         int x = Int32.Parse(System.Console.ReadLine( )), rang;
         //rang = RechSeq1( table, x );
         //rang = RechSeq2( table, x );
         //rang = RechSeq3( tableSent, x );
         rang = RechSeq4( table, x );
         if (rang >0)
           System.Console.WriteLine("Elément "+x+" trouvé en : "+rang);
        else System.Console.WriteLine("Elément "+x+" non trouvé !");
           System.Console.Read();
}
}

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 C# à implanter :

class ApplicationRechLinTrie {
     static void AfficherTable ( int[] table )
   {
             // Affichage du tableau
    }
    static void InitTable ( )
   {
                 // remplissage du tableau
    }
    static void TriInsert ( )
   {
          // sous-programme de Tri par insertion :
   }
   static int RechSeqTri1( int[] t, int Elt )
    {
        // Version Tantque
     }
static int RechSeqTri2( int[] t, int Elt )
{
        // Version pour
}

static void Main(string[ ] args)
{
       ..........
}
}

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

static void Main(string[ ] args)
{
               InitTable ( );
               System.Console.WriteLine("Tableau initial :");
               AfficherTable (table );
               int x = Int32.Parse(System.Console.ReadLine( )), rang;
               //rang = RechSeqTri1( table, x );
               rang = RechSeqTri2( table, x );
               if (rang >0)
                 System.Console.WriteLine("Elément "+x+" trouvé en : "+rang);
               else System.Console.WriteLine("Elément "+x+" non trouvé !");
              System.Console.Read();
}

Remonter