Principes de programmation

Recherche

2526 · Dekens Antoine

Recherches linéraires

ou recherche séquentielle

Définition

La recherche séquentielle ou recherche linéaire est un algorithme pour trouver une valeur dans une liste. Elle consiste simplement à considérer les éléments de la liste les uns après les autres, jusqu'à ce que l'élément soit trouvé, ou que toutes les cases aient été lues. Elle est aussi appelée recherche par balayage.

Wikipédia

Principe

La recherche séquentielle consiste à prendre les éléments de la liste les uns après les autres, jusqu'à avoir trouvé la cible, ou avoir épuisé la liste.

Propriétés

Structure des données libre (avec ou sans tri)
Efficacité et performance réduite sur un large panel de données

Exemple non trié

Le but est trouver la présence du nombre 128 dans un tableau contenant d'autres nombres :

$data: [ 1024, 8, 32, 256, 128, 512, 64, 16 ];
$toFind: 128;

while

On prévoit une variable $found qui contiendra notre donnée si elle est trouvée dans notre tableau depuis une boucle while :

$data = [ 1024, 8, 32, 256, 128, 512, 64, 16 ];
$toFind = 128;
$found = null;
$length = count( $data );

$i = 0;
while( $i < $length ){
  // Vérifie si notre nombre est strictement égale
  // à la donnée positionnée à $i dans notre tableau.
  if( $toFind === $data[ $i ] ){
    $found = $data[ $i ];
  }

  $i++;
}

echo $found;

Amélioration

Pour le moment, notre boucle traverse toute les données de notre tableau même si nous avons trouvé une concordance. On pourrait ajouter une deuxième condition qui le vérifie et permettra de stopper notre boucle :

$data = [ 1024, 8, 32, 256, 128, 512, 64, 16 ];
$toFind = 128;
$found = null;
$length = count( $data );

$i = 0;
while( ( $i < $length ) AND ( $found === null ) ){
  if( $toFind === $data[ $i ] ){
    $found = $data[ $i ];
  }

  $i++;
}

echo $found;

Break

L'instruction break permet de mettre fin à l'éxécution d'une boucle de manière manuelle. L'avantage est que cela nous évite d'écrire des conditions supplémentaires :

Il est possible de passer un nombre représentant le nombre de boucles à stopper (structure imbriquée)

break

$data = [ 1024, 8, 32, 256, 128, 512, 64, 16 ];
$toFind = 128;
$found = null;
$length = count( $data );

$i = 0;
while( $i < $length ){
  if( $toFind === $data[ $i ] ){
    $found = $data[ $i ];

    // On ajoute le break dans notre condition d'égalité
    break;
  }

  $i++;
}

echo $found;

Exemple trié

Dans le cas d'un tableau trié de manière croissante, nous pouvons ajouter une condition : si notre nombre recherché est plus grand ou égale à la valeur comparée alors nous sortons de la boucle :

$data: [ 8, 16, 32, 64, 128, 256, 512, 1024 ];
$toFind: 128;

$data = [ 8, 16, 32, 64, 128, 256, 512, 1024 ];
$toFind = 128;
$found = null;
$length = count( $data );

$i = 0;
while( ( $i < $length ) AND ( $found === null ) AND ( $toFind >= $data[ $i ] ) ){
  if( $toFind === $data[ $i ] ){
    $found = $data[ $i ];
    break;
  }

  $i++;
}

echo $found;

Amélioration

En utilisant break nous pouvons garder notre condition de boucle plus lisible tout en gardant une condition de sortie :

$data = [ 8, 16, 32, 64, 128, 256, 512, 1024 ];
$toFind = 128;
$found = null;
$length = count( $data );

$i = 0;
while( ( $i < $length ) AND ( $toFind >= $data[ $i ] ) ){
  if( $toFind === $data[ $i ] ){
    $found = $data[ $i ];
    break;
  }

  $i++;
}

echo $found;

Exercice A

Sur base du tableau suivant, ecrire une boucle de type for pour :

trouver le nombre 256
combien d'éléments strictement inférieurs
combien d'éléments strictement supérieurs
afficher trois phrase différentes présentant les résultats

$data = [ 1024, 8, 32, 256, 128, 512, 64, 16 ];

Exercice B

Sur base du tableau suivant, ecrire une boucle de type foreach pour :

trouver le nombre 432
calculer la moyenne des éléments strictement inférieurs
afficher 2 phrase différentes présentant les résultats

$data = [ 8, 16, 32, 64, 128, 256, 512, 1024, 2048 ];

Recherches dichotomiques

Définition

La recherche dichotomique, ou recherche par dichotomie est un algorithme de recherche pour trouver la position d'un élément dans un tableau trié.

Wikipédia

Principe

Comparer l'élément avec la valeur de la case au milieu du tableau ; si les valeurs sont égales, la tâche est accomplie, sinon on recommence dans la moitié du tableau pertinente.

Propriétés

Structure des données triée
Efficacité et performance sur un large panel de données

Mise en place

Nous avons besoin de prévoir deux bornes, une commençant à 0 et l'autre la longueur de notre tableau moins un. Ensuite nous pouvons écrire une boucle while avec cette condition :

$data = [ 8, 16, 32, 64, 128, 256, 512, 1024 ];
$toFind = 128;
$found = null;

// Notre borne de départ
$left = 0;

// Notre borne de fin
$right = count( $data ) - 1;

while( $left <= $right ) {
  // Calcule la position de la case entre les 2 bornes
  $i = (int) ( ( $right + $left) / 2 );

  if( $toFind === $data[ $i ] ){
    $found = $data[ $i ];
    break;

  } else{

    if( $toFind < $data[ $i ] ){
      $right = $i - 1;

    } else {
      $left = $i + 1;
    }
  }
}

echo $found;

Exercice B

Sur base du tableau suivant, utiliser une recherche dichotomique pour :

trouver le pokemon ayant le niveau 32

$pokemons = [
  'roucool' => 4,
  'pikachu' => 8,
  'carabaffe' => 16,
  'onix' => 32,
  'dracaufeu' => 64,
  'mewtwo' => 128,
];

Exercice C

Dans un nouveau dossier d'exercice, créer un fichier index.php avec un tableau permettant de passer un nombre via un formulaire et récupérer sa valeur dans un fichier search.php pour effectuer une recherche dichotomique sur le tableau suivant :

$pokemons = [
  'roucool' => 4,
  'pikachu' => 8,
  'carabaffe' => 16,
  'onix' => 32,
  'dracaufeu' => 64,
  'mewtwo' => 128,
];