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 et on compare la valeur avec la valeur au milieu du tableau.
Au départ . Trois situations se présentent :
- : la recherche est terminée.
- : il faut poursuivre la recherche dans la moitié gauche de l'intervalle .
- : il faut poursuivre la recherche dans la moitié droite de l'intervalle .
Dans les deux derniers cas, la recherche continue avec le même procédé, on divise à nouveau l'intervalle 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, la 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])
j <- 0
var tab_start
var tab_end
var 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[j] = T[i]
j++
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.