Js algo td4

Introduction

En algorithmique, la recherche dichotomique relève du principe diviser pour régner qui est ici pris au pied de la lettre puisque l'intervalle de recherche est divisé en deux sous-intervalles de même taille.

À chaque étape de l'algorithme, on calcule le milieu m de l'intervalle de recherche $I$ et on compare la valeur $x$ avec la valeur $T[m]$ au milieu du tableau.

Au départ $I=[1\,,n]$. Trois situations se présentent :

1. $x=T[m]$ : la recherche est terminée.
2. $x<T[m]$ : il faut poursuivre la recherche dans la moitié gauche de l'intervalle $I$.
3. $x>T[m]$ : il faut poursuivre la recherche dans la moitié droite de l'intervalle $I$.

Dans les deux derniers cas, la recherche continue avec le même procédé, on divise à nouveau l'intervalle $I$ en deux moitiés et ainsi de suite jusqu'à ce que l'intervalle de recherche soit réduit à un seul terme.

L'algorithme est la stricte application de ce principe.

Pseudo-code

Soit T un tableau de noms:

var T = new Array("Alain", "Antoine", "Bernard", "Christine", "Colin", "François", "Gérard", "Guy", "Léa", "Léon", "Louis", "Nathalie", "Serge", "Sylvain", "Sylvie", "Vincent");

Exercice 1

Écrire la fonction compare_char qui prend en paramètres deux caractères a et b et qui renvoie:

• une valeur négative si a < b;
• 0 si a == b;
• une valeur positive si a > b;

Solution

FONCTION compare_char(a, b)
   SI a < b 
      RETOURNE -1;
   SINON SI a > b {
      RETOURNE 1;
   FIN SI
   RETOURNE 0;
FIN FONCTION

Exercice 2

Écrire la fonction compare_string qui prend en paramètres deux chaînes de caractères x et y et qui renvoie:

• une valeur négative si x < y;
• 0 si x == y;
• une valeur positive si x > y;

Cette fonction doit comparer chacune des lettres des deux chaînes tant qu'il y a égalité !

Solution

FONCTION compare_string(a, b)
   VAR
      i : entier
      compare : entier

   i <- 0;

   TANT QUE i < len(a) ET i < len(b) FAIRE
      compare <- compare_char(a[i], b[i]);
      SI compare != 0
         RETOURNE  compare;
      FIN SI
      i++;
   FIN TANT QUE
   RETOURNE 0;
FIN FONCTION

Exercice 3

Écrire la fonction get_value qui prend en paramètres le tableau T ainsi qu'une chaîne de caractères, x. Cette fonction, qui utilise la recherche par dichotomie, renvoie un tableau qui correspond à la moitié du tableau T où se trouverait la valeur x, ou bien, l'index de la valeur recherchée.

Solution

FONCTION get_half(T, x) {
   VAR
      half : entier
      compare : entier
      j : entier
      i : entier
      tab_start : entier
      tab_end : entier
      resultat : tableau 

   half <- arrondi(len(t) / 2);
   compare <- compare_string(T[half],x)
   j <- 0
   SI compare = 0 ALORS
      RETOURNE half
   SINON
      SI compare < 0 ALORS
         tab_start <- 0
         tab_end <- half
      SINON
         tab_start <- half
         tab_end <- len(T)
      FIN SI
      POUR i = tab_start JUSQU'A i < tab_end {PAR PAS DE 1}
         resultat[i] = T[i]
      FIN POUR
      RETOURNE resultat
   FIN SI
FIN FONCTION

Exercice 4

Écrire la fonction main qui prend en paramètre une chaîne de caractères name et qui utilise les fonctions précédentes pour retourner:

• l'index de la chaîne name;
• la phrase suivante La chaîne n'existe pas.

Application en JavaScript

Exercice 1

Écrire la fonction compare_char.

Solution

function compare_char(a, b) {
   if (a < b) {
      return -1;
   } else if (a > b) {
      return 1;
   }
   return 0;
}

Exercice 2

Écrire la fonction compare_string.

Pour cela, vous pouvez vous aider de la fonction String.charAt(num) dont voici la documentation:

Syntax

string.charAt(num)

The charAt() method returns the character located at the indexed, num, position passed. This indexing is done from left to right starting with the 0 (zero) position.
If the num passed is not a valid index in the string, -1 is returned.

Solution

function compare_string(a, b) {
   var i = 0;
   while(i < a.length && i < b.length){
      var charA = a.charAt(i);
      var charB = b.charAt(i);
      var compare = compare_char(charA, charB);
      if(compare != 0){
         return  compare;
      }
      i++;
   }
   return 0;
}

Exercice 3

Écrire la fonction get_value.

Solution

function get_half(T, x) {
	var half = Math.round(T.length / 2);
	var half_value = T[half];
	var compare = compare_string(x, half_value);
	var tab_start;
	var tab_end;
	var j = 0;
	if (compare == 0) {
		return half;
	} else {
		if (compare < 0) {
			tab_start = 0;
			tab_end = half;
		} else {
			tab_start = half;
			tab_end = T.lenght;
		}
		var resultat = new Array();
		for (var i = tab_start; i < tab_end; i++) {
			resultat[j] = T[i];
			j++;
		}
		return resultat;
	}
}

Exercice 4

Écrire la fonction main.

Pour tester le type d'une variable, vous pouvez utiliser le mot clé instanceof.

Par exemple:

var T = new Array();

if(T instanceof Array){
   console.log("Je suis un tableau");
}

Affichera Je suis un tableau.