Algorithme de récupération de la structure des données javascript et compétences algorithm_javascript

Il existe deux façons de trouver des données : la recherche séquentielle et la recherche binaire. La recherche séquentielle fonctionne sur des listes contenant des éléments disposés de manière aléatoire. La recherche binaire fonctionne sur une liste triée d'éléments. La recherche binaire est plus efficace, mais elle doit être un ensemble trié d'éléments de liste.

1 : Recherche séquentielle
La recherche séquentielle consiste à juger les éléments de la liste un par un en commençant par le premier élément de la liste jusqu'à ce que le résultat souhaité soit trouvé, ou que l'élément souhaité ne soit trouvé qu'à la fin de la liste.

Le code est le suivant :

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return true;
    }
  }
  return false;
}

On peut également renvoyer la fonction de recherche séquentielle qui correspond à la position de l'élément. Le code est le suivant :

function seqSearch(data,arr) {
  for(var i = 0; i < arr.length; ++i) {
    if(arr[i] == data) {
      return i;
    }
  }
  return -1;
}

Deux : Trouver les valeurs minimales et maximales

L'algorithme pour trouver la valeur minimale dans un tableau est le suivant :

1. Attribuez le premier élément du tableau à une variable et utilisez cette variable comme valeur minimale.
2. Commencez à parcourir le tableau en commençant par le deuxième élément et en le comparant à la valeur minimale actuelle.
3. Si la valeur de l'élément actuel est inférieure à la valeur minimale actuelle, définissez l'élément actuel sur la nouvelle valeur minimale.
4. Passez à l'élément suivant et répétez l'étape 3.
5. À la fin du programme, ce qui est stocké dans cette variable est la valeur minimale.

Le code est le suivant :

function findMin(arr) {
  var min = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

L'algorithme pour trouver la valeur maximale est similaire à la valeur minimale ci-dessus. Tout d'abord, définissez le premier élément du tableau sur la valeur maximale, puis effectuez une boucle pour comparer chaque élément restant du tableau avec la valeur maximale actuelle. la valeur de l'élément actuel est supérieure à la valeur maximale actuelle, puis attribuez la valeur de l'élément à la valeur maximale. Le code est le suivant :

function findMax(arr) {
  var max = arr[0];
  for(var i = 1; i < arr.length; ++i) {
    if(arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
 }

Trois : méthode de recherche binaire.

Si les données que vous recherchez sont ordonnées, l'algorithme de recherche binaire est plus efficace que l'algorithme de recherche séquentielle. Le principe de base de l'algorithme de recherche binaire est le suivant :

1. Définissez la première position du tableau sur la limite inférieure (0).
2. Définissez la position du dernier élément du tableau sur la limite supérieure (la longueur du tableau moins 1).
3. Si la limite inférieure est égale ou inférieure à la limite supérieure, procédez comme suit :
A. Définissez le point médian sur (limite supérieure plus limite inférieure) divisé par 2.
B. Si l'élément au milieu est plus petit que la valeur de la requête, définissez la limite inférieure sur l'indice de l'élément du milieu plus 1.
C. Si l'élément au milieu est supérieur à la valeur de la requête, définissez la limite supérieure sur l'indice de l'élément du milieu moins 1.
D. Sinon, l'élément médian correspond aux données à trouver et peut être renvoyée.

Le code est le suivant :

// 二分查找算法
function binSearch(data,arr) {
var lowerBound = 0;
  var upperBound = arr.length - 1;
  while(lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound)/2);
    if(arr[mid] < data) {
      lowerBound = mid + 1;
    }else if(arr[mid] > data) {
      upperBound = mid - 1;
    }else {
      return mid;
    }
  }
  return -1;
}
 // 快速排序
function qSort(list) {
  if(list.length == 0) {
    return [];
  }
  // 存储小于基准值的值
  var left = [];
  // 存储大于基准值的值
  var right = [];
  var pivot = list[0];
  for(var i = 1; i < list.length; i++) {
    if(list[i] < pivot) {
      left.push(list[i]);
    }else {
      right.push(list[i])
    }
  }
  return qSort(left).concat(pivot,qSort(right));
}
 // 测试代码
var numbers = [0,9,1,8,7,6,2,3,5,4];
var list = qSort(numbers);
console.log(binSearch(6,list));

4 : Calculez le nombre de répétitions
Lorsque la fonction binSearch() de l'algorithme de recherche binaire trouve une certaine valeur, s'il y a d'autres mêmes valeurs dans l'ensemble de données, alors la fonction sera positionnée à proximité de valeurs similaires. apparaît. Le côté gauche ou droit de la valeur trouvée.

Ensuite, notre solution la plus simple est d'écrire deux boucles, une qui parcourt simultanément l'ensemble de données vers le bas ou vers la gauche, en comptant le nombre de répétitions, puis, en parcourant vers le haut ou vers la droite, en comptant le nombre de répétitions ; Le code est le suivant :

// 计算重复次数
function count(data,arr) {
  var count = 0;
  var arrs = [];
  var position = binSearch(data,arr);
  if(position > -1) {
    ++count;
    arrs.push({"index":count});
    for(var i = position -1; i > 0; --i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
    for(var i = position + 1; i < arr.length; ++i) {
      if(arr[i] == data) {
        ++count;
        arrs.push({"index":count});
      }else {
        break;
      }
    }
  }
  return arrs;
}
 // 测试重复次数的代码
var arr = [0,1,1,1,2,3,4,5,6,7,8,9];
var arrs = count(1,arr);
console.log(arrs);
console.log(arrs.length);

Comme indiqué ci-dessous :