Pas même un seul pass d’une journée, lorsque nous n’avons pas à rechercher quelque chose dans notre vie quotidienne, clés de voiture, livres, stylo, chargeur mobile et quoi d’autre. La même chose est la vie d’un ordinateur, il y a tellement de données stockées dedans, que chaque fois qu’un utilisateur demande des données, l’ordinateur doit rechercher sa mémoire pour rechercher les données et les mettre à la disposition de l’utilisateur. Et l’ordinateur dispose de ses propres techniques pour rechercher rapidement sa mémoire, que vous pouvez en apprendre davantage dans notre série de didacticiels sur le système d’exploitation.
Que se passe-t-il si vous devez écrire un programme pour rechercher un nombre donné dans un tableau? Comment allez-vous le faire?
Eh bien, pour rechercher un élément dans un tableau donné, il existe deux algorithmes populaires disponibles:
- Recherche linéaire
- Recherche binaire
Recherche linéaire
La recherche linéaire est un algorithme de recherche très simple et simple. Dans la recherche linéaire, nous recherchons un élément ou une valeur dans un tableau donné en parcourant le tableau depuis le début, jusqu’à ce que l’élément ou la valeur souhaitée soit trouvée.
Il compare l’élément à rechercher avec tous les éléments présents dans le tableau et lorsque l’élément est mis en correspondance avec succès, il renvoie l’index de l’élément dans le tableau, sinon il renvoie -1.
La recherche linéaire est appliquée sur des listes non triées ou non ordonnées, lorsqu’il y a moins d’éléments dans une liste.
Caractéristiques de l’algorithme de recherche linéaire
- Il est utilisé pour les petites listes d’éléments non triées et non ordonnées.
- Il a une complexité temporelle de O(n), ce qui signifie que le temps dépend linéairement du nombre d’éléments, ce qui n’est pas mauvais, mais pas si bon aussi.
- Il a une implémentation très simple.
Nous allons implémenter l’algorithme de recherche linéaire dans le prochain tutoriel.
Recherche binaire
La recherche binaire est utilisée avec un tableau ou une liste triés. Dans la recherche binaire, nous suivons les étapes suivantes:
- Nous commençons par comparer l’élément à rechercher avec l’élément au milieu de la liste / du tableau.
- Si nous obtenons une correspondance, nous renvoyons l’index de l’élément du milieu.
- Si nous n’obtenons pas de correspondance, nous vérifions si l’élément à rechercher est inférieur ou supérieur à la valeur de l’élément du milieu.
- Si l’élément / le nombre à rechercher a une valeur supérieure au nombre du milieu, nous choisissons les éléments sur le côté droit de l’élément du milieu (comme la liste / le tableau est trié, donc à droite, nous aurons tous les nombres supérieurs au nombre du milieu), et recommençons à partir de l’étape 1.
- Si l’élément / le nombre à rechercher a une valeur inférieure au nombre du milieu, nous choisissons les éléments sur le côté gauche de l’élément du milieu et recommençons à partir de l’étape 1.
La recherche binaire est utile lorsqu’il y a un grand nombre d’éléments dans un tableau et qu’ils sont triés.
Une condition nécessaire pour que la recherche binaire fonctionne est que la liste / le tableau doit être trié.
Caractéristiques de la recherche binaire
- Il est idéal de rechercher dans de grands tableaux triés.
- Il a une complexité temporelle de O (log n) qui est une très bonne complexité temporelle. Nous en discuterons en détail dans le tutoriel de recherche binaire.
- Il a une implémentation simple.