1
votes

Recherche linéaire récursive en utilisant Javascript

J'essaie d'implémenter la recherche linéaire de manière récursive en utilisant Javascript.

LinearSearchRecursively(ArrayGiven, x, startingValue)

Signature de fonction - quelque chose comme ceci:

Given Array A = [1,2,3,4,5,6]

Si la valeur est found puis renvoie l'index else return -1, mais y parvient de manière récursive.

Apprécierait si vous pouvez attacher un jsbin ou jsfiddle en cours d'exécution.

javascript recursion linear-search

0 commentaires

3 Réponses :

0
votes

Je ferais quelque chose comme ceci: voici le lien jsbin:

https: //jsbin.com/lijitet/8/edit?js,console

/**
 * Linear Search : Recursion
 * Returns index if found -1 otherwise
 * Procedure LinearSearch(Array A, int x, int i)
 * n = A.length and i is starting position of array
 * if (A[i] === x) return i
 * if (i > n) LinearSearch(A, x, i++)
  * 
  */
 function LinearSearchRecursively(ArrayGiven, x, i) {
     const arrayLength = ArrayGiven.length;

     if (i > (arrayLength - 1)) {
       return -1;
     }
     if(ArrayGiven[i] === x) {
       return i;
     }
     return LinearSearchRecursively(ArrayGiven, x, i+1); 
 }

 // write your test cases here :
 const testArray = [ 1, 2, 3, 4, 5, 6, 7];

 console.log(`Missing Element : ${LinearSearchRecursively(testArray, 7, 0)}`);

N'hésitez pas à ajouter. merci.

0 commentaires

1
votes

Vous pouvez changer la signature de la fonction, car l'appel de la fonction de recherche devrait être possible sans prendre d'index initial pour la recherche.

function linearSearchRecursively([a, ...rest], x, i = 0) {
    if (a === x) return i;
    if (!rest.length) return -1;
    return linearSearchRecursively(rest, x, i + 1);
}

console.log(linearSearchRecursively([1, 2, 3, 4, 5, 6, 7], 7));
console.log(linearSearchRecursively([1, 2, 3, 4, 5, 6, 7], 9));
console.log(linearSearchRecursively([], 7));

Une autre solution pourrait être d'utiliser une déstructuration pour le tableau et de vérifier par rapport au premier élément.

function linearSearchRecursively(a, x, i = 0) {
    if (i >= a.length) return -1;
    if (a[i] === x) return i;
    return linearSearchRecursively(a, x, i + 1);
}

console.log(linearSearchRecursively([1, 2, 3, 4, 5, 6, 7], 7));
console.log(linearSearchRecursively([1, 2, 3, 4, 5, 6, 7], 9));
console.log(linearSearchRecursively([], 7));

0 commentaires

2
votes

Vous pouvez le faire en utilisant la déstructuration de tableau pour obtenir la tête et la queue de votre tableau.

Vous comparez ensuite la tête, si elle est égale à votre valeur, vous retournez l'index jusqu'à présent, sinon, vous appelez le récursif fonction avec la queue et l'index incrémentés.

Votre condition d'arrêt est lorsque le tableau est vide, auquel cas vous retournez -1.

Ici, j'enveloppe la fonction récursive et son appel avec une fonction externe qui a une API plus agréable, sans l'index.

function linearSearch(arr, value) {
  function linearSearchRec(list, idx) {
    if (!list.length) return -1;
    const [head, ...tail] = list;
    if (value === head) return idx;
    else return linearSearchRec(tail, idx + 1);
  }
  return linearSearchRec(arr, 0);
}

console.log(linearSearch([1,2,3,4,5,6], 1));
console.log(linearSearch([1,2,3,4,5,6], 4));
console.log(linearSearch([1,2,3,4,5,6], 10));

0 commentaires