0
votes

Recherche binaire, méthode de récursion, renvoyant la mauvaise sortie - JS

J'essaie de faire une recherche binaire de base d'une valeur dans un tableau à l'aide de la méthode de la récursivité. J'ai utilisé la méthode itérative sur ce même tableau et j'ai obtenu la bonne sortie. Mais ce code renvoie false (élément n'est pas dans le tableau), que l'entrée soit dans la matrice ou non. xxx

javascript recursion binary-search

1 commentaires

La recherche binaire a une condition préalable que la matrice est commandée. BTW, votre recherche binaire semble très bonne!

3 Réponses :

1
votes

Votre tableau doit être trié pour une recherche binaire. Il vérifie si 91 est au milieu, non puis depuis 91 est supérieur à 7, il vérifie [moyen + 1, fin].

0 commentaires

1
votes

Vous devez juste trier votre tableau avant d'effectuer la recherche binaire. Donc, sur la ligne 16 où vous créez vos exemples données simplement ajouter .sort () à la fin.

La recherche binaire n'est pas possible avec un ensemble de données non formé.

Je suppose que vous faites cela juste pour l'apprentissage, mais je tiens à souligner que la plupart des langages de programmation utiliseront une recherche binaire sous la hotte si votre liste est triée et que vous effectuez une recherche. C'est pourquoi il est important de le comprendre comme un concept, mais il serait incroyablement improbable que vous devriez jamais avoir à la mettre en œuvre vous-même.



                                                                    
                                    
                                    
                                        0 commentaires


                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Comme indiqué dans les commentaires, votre tableau doit être commandé pour que la recherche binaire fonctionne, pense aux étapes de votre tableau fourni ( [28, 91, 30, 33, 2, 7, 88, 90, 70, 44, 40, 41]  code>) 
 Dans la première étape, il prendra la valeur au milieu de la matrice ( 7  code>) qui sera inférieure à la valeur que vous regardez ( 91  code>), il réduira votre matrice à ( [88, 90, 70, 44, 40, 41]  code>), puis vous pouvez remarquer pourquoi votre article est introuvable.  p> 
 Utiliser  Trier  code> devant votre tableau corrige le problème :)  p> 
 5 7
8 70
10 40
11 41
L'élément n'a pas été trouvé dans ARR  P> 
  p> 


let recursionFunction = function (arr, x, start, end) {
  if (start > end) {
    return false
  }
  let mid = Math.floor((start + end)/2)
  console.log(mid, arr[mid])
  if (arr[mid] == x) {
    return true
  }
  if (arr[mid] > x) {
    return recursionFunction(arr, x, start, mid-1)
  } else {
    return recursionFunction(arr, x, mid+1, end)
  }
}
let x = 91
// with sort, it will work.
let arr = [28, 91, 30, 33, 2, 7, 88, 90, 70, 44, 40, 41].sort();
if (recursionFunction(arr, x, 0, arr.length-1)) {
  console.log("element is found in arr")
} else {
  console.log('element is not found in arr')
}

                                

                                                                    
                                    
                                    
                                        0 commentaires