Sujet Précédent Sujet Suivant

Problème algorithme dichotomique

Résolu/Fermé
a.b - Modifié le 25 janv. 2021 à 19:55
jordane45 Messages postés 37267 Date d'inscription mercredi 22 octobre 2003 Statut Modérateur Dernière intervention 23 mars 2023 - 25 janv. 2021 à 20:40
Bonjour,

J'essaye d'implémenter ce code mais je n'arrive pas à comprendre pourquoi. L'aide serait le bienvenue. 


let tab = [4,3,2,5,2,4];
function findM(tab) {
    return Math.floor(tab.length / 2)
}

let m = 0;
let milieu = findM(tab)

function search(tab,x,m) {
    if(x < tab[m]) {
        leftTab = tab.slice(0,m)
        ml = findM(leftTab)
        search(leftTab,x,ml)
    } else {
        rightTab = tab.slice(m,tab.length)
        mr = findM(rightTab)
        search(rightTab,x,mr)
    }
}

console.log(search(tab,2,milieu))


Voilà à l'exécution : 

alfa@MacBook-Pro-de-Alpha algo_niv2 % node ./exoalgo1.js
/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:114
        rightTab = tab.slice(m-1,tab.length-1)
                       ^

RangeError: Maximum call stack size exceeded
    at Array.slice (<anonymous>)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:114:24)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
    at search (/Users/alfa/Documents/L1-Dev/Modules/algo_niv2/exoalgo1.js:116:9)
alfa@MacBook-Pro-de-Alpha algo_niv2 %


Je vous remercie d'avance.

Configuration: Macintosh / Chrome 84.0.4147.105

1 réponse

Réponse 1 / 1
jordane45 Messages postés 37267 Date d'inscription mercredi 22 octobre 2003 Statut Modérateur Dernière intervention 23 mars 2023 4 550
25 janv. 2021 à 20:40
Bonjour,

Pour faire une recherche par dichotomie.. il faudrait déjà que ton tableau soit trié et ne contienne pas de valeurs en doublons.
En plus, dans ton code actuel, tu ne sorts jamais... même si tu trouves le bon résultat...
Donc, ben.. tu fais une boucle infinie

Essaye ça 
    let tab = [1,2,3,4,5,6,7,8];
    function findM(tbl) {
      return Math.floor(tbl.length / 2)
    }

    var m = 0;
    var milieu = findM(tab);

    function search(tbl,x,m) {
    console.log(tbl,x,m);
      let tm = typeof(tbl[m])!='undefined' ? tbl[m] : null;
      if(!tm) return false;
      if(tm == x){
        console.log("Valeur trouvée à l'indice ",m);
        return true;
      }else if(x < tm) {
          let leftTab = tbl.slice(0,m);
          let ml = findM(leftTab);
          search(leftTab,x,ml);
      } else {
          let rightTab = tbl.slice(m,tbl.length);
          let mr = findM(rightTab);
          search(rightTab,x,mr);
      }
    }
    
    console.log(search(tab,2,milieu));

1