Algorithmes : recherche linéaire et recherche binaire

Certains algorithmes simples introduisent des concepts de base de logique et de structure de données, tandis que d'autres visent une plus grande complexité.

Les algorithmes de recherche sont utiles pour localiser des informations dans des volumes de données, comme trouver un contact dans un annuaire téléphonique ou un fichier sur un ordinateur.

En ce sens, cet article vise à présenter une introduction aux concepts impliquant les algorithmes de recherche linéaire et de recherche binaire.

1. Recherche linéaire

• Parcourez une liste séquentiellement pour trouver un élément
• Un exemple serait de rechercher un numéro spécifique dans un tableau

L'Algorithme de recherche linéaire, dans un énoncé narratif, signifie avoir un tableau d'entiers et une valeur qui sera la référence pour la recherche, appelée cible, qui seront les paramètres d'entrée. En ce sens, il existe une fonction qui reçoit ces valeurs, et avec cela, elle parcourt d'abord chaque position de ce tableau jusqu'à la taille maximale des positions existantes, en utilisant principalement un for pour cela, et ensuite, avec un if, elle est conditionné le contrôle de : si chaque position a une valeur égale à la cible. Si la valeur est trouvée, la fonction renvoie l'index de cette position, ou renvoie -1, représentant les cas non trouvés.

Un exemple utilisant JavaScript serait :

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

Par conséquent, cet algorithme vise à renvoyer la position, ou index, où se trouve l'élément, ou même, il localise simplement le premier élément correspondant, sans avoir besoin de continuer après l'avoir trouvé. Ce comportement se produit en raison des instructions de l'algorithme qui, lorsque sa condition est satisfaite, exécute le retour avec l'index de l'élément, puis quitte la boucle, mettant fin à la fonction.

Cet algorithme peut être utile dans les scénarios où il existe des listes petites ou non ordonnées. Chaque élément peut devoir être parcouru et il n'y a pas d'utilisation de mémoire supplémentaire.

2. Recherche binaire

• Faites défiler une liste ordonnée pour trouver un élément
• Un exemple serait de rechercher un numéro spécifique dans un tableau

L'Algorithme de recherche binaire est une forme d'algorithme plus efficace pour trouver une valeur donnée dans un tableau trié. Cela fonctionne en divisant à plusieurs reprises la plage de recherche en deux, ce qui la rend nettement plus rapide que la recherche linéaire pour de grands ensembles de données. La recherche binaire a une complexité O(log n), tandis que la recherche linéaire est O(n).

A titre d'exemple en JavaScript, nous avons :

function linearSearch(array, target) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === target) {
      return i; 
    }
  }
  return -1; 
}

La logique consiste à commencer avec deux pointeurs, un au début (bas) et l'autre à la fin (haut) du tableau. Ainsi, l'indice du milieu est calculé const middle = Math.floor((low high) / 2). Avec cela, l'élément du milieu est comparé à la cible à chaque étape : si l'élément du milieu est égal à la cible, l'index est renvoyé. Cependant, si l'élément du milieu est plus petit que la cible, ou si l'élément du milieu < cible, implique de rejeter les plus petits nombres, en plaçant le début comme bas = milieu 1. Si l'élément du milieu, à son tour, est supérieur au milieu cible > cible, les nombres supérieurs à la cible sont ignorés, ajustant l'index final à haut = milieu - 1. Ce processus est répété jusqu'à ce que la cible soit trouvée ou lorsque la plage devient invalide, dans le cas bas > élevé.

La recherche binaire peut être efficace pour rechercher des données ordonnées, comme dans un dictionnaire alphabétique ou un ensemble de dates ordonnées. Ils ont tendance à être plus rapides et plus efficaces, car le problème peut être divisé en sous-problèmes plus petits à chaque itération.

Par conséquent, il est entendu que la recherche linéaire est simple et fonctionne sur de petites listes. La recherche binaire est beaucoup plus efficace, mais nécessite des données ordonnées.

Comprendre le fonctionnement des différents algorithmes et leurs contextes d'utilisation est une étape importante vers la construction de solutions informatiques efficaces. Essayez de mettre en œuvre et d'analyser ces méthodes, et découvrez comment ces stratégies peuvent être adaptées pour résoudre les défis du monde réel. =)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!