Recherche dans la structure de données : différentes méthodes de recherche expliquées
Publié: 2021-05-03Le réseau de communication s'étend, et donc les gens utilisent Internet ! Les entreprises se digitalisent pour une gestion efficace. Les données générées sur Internet augmentent et les ensembles de données deviennent donc complexes. Il est essentiel d'organiser, de gérer, d'accéder et d'analyser les données avec soin et efficacité, une structure de données est la technique la plus utile, et l'article se concentre sur la même chose !
Table des matières
Structure de données
En informatique, les structures de données sont à la base des types de données abstraits (ADT), où ADT est la forme logique du type de données. La disposition physique du type de données est implémentée à l'aide de la structure de données. Différents types de structure de données sont utilisés pour différents types d'applications ; certains sont spécialisés dans des tâches particulières.
La structure de données est un ensemble de valeurs de données et de relations entre elles, d'opérations et de fonctions applicables aux données. Il aide à organiser, gérer et stocker les données dans un format particulier. Ainsi, les utilisateurs peuvent avoir un accès facile et modifier les données efficacement.
Les structures de données aident à gérer de grandes quantités de données, telles que des bases de données massives. Des algorithmes efficaces sont construits sur la base de structures de données efficaces. Outre un stockage efficace, les structures de données sont également responsables de la récupération efficace des informations de la mémoire stockée. Il comprend un tableau, une liste liée, un pointeur, une recherche, une pile, un graphique, une file d'attente, une structure, des programmes, un tri, etc.
L'article couvre le concept de recherche dans la structure de données et ses méthodes. Deux exemples d'algorithmes sont expliqués en détail pour bien comprendre le concept. Pour approfondir les connaissances, les compétences et l'expertise, des cours en ligne sur la structure des données sont disponibles, mentionnés à la fin de l'article.
Qu'est-ce que la recherche dans la structure de données ?
Le processus de recherche des informations souhaitées à partir de l'ensemble d'éléments stockés sous la forme d'éléments dans la mémoire de l'ordinateur est appelé "recherche dans la structure de données". Ces ensembles d'éléments se présentent sous diverses formes, telles qu'un tableau, un arbre, un graphique ou une liste chaînée. Une autre manière de définir la recherche dans la structure de données consiste à localiser l'élément souhaité de caractéristiques spécifiques dans une collection d'éléments.
Méthodes de recherche
La recherche dans la structure de données peut être effectuée en mettant en œuvre des algorithmes de recherche pour vérifier ou récupérer un élément à partir de n'importe quelle forme de structure de données stockée. Ces algorithmes sont classés en fonction de leur type d'opération de recherche, tels que :
- Recherche séquentielle
Le tableau ou la liste d'éléments est parcouru séquentiellement tout en vérifiant chaque composant de l'ensemble.
Par exemple, Recherche linéaire.
- Recherche d'intervalle
Les algorithmes conçus explicitement pour la recherche dans des structures de données triées sont inclus dans la recherche par intervalle. L'efficacité de ces algorithmes est bien meilleure que celle des algorithmes de recherche linéaire.
Par exemple, Recherche binaire, Recherche logarithmique.
Ces méthodes sont examinées en fonction du temps pris par un algorithme pour rechercher un élément correspondant à l'élément de recherche dans les collections de données et sont données par,
- Le meilleur moment possible
- Le temps moyen
- Le pire moment
Les principales préoccupations concernent les temps les plus défavorables qui conduisent à des prédictions garanties des performances de l'algorithme et sont également faciles à calculer par rapport aux temps moyens.
Pour illustrer des exemples et des concepts dans cet article, 'n' éléments de la collecte de données dans n'importe quel format de données sont pris en compte. Les opérations dominantes sont utilisées pour simplifier l'analyse et la comparaison d'algorithmes. Pour effectuer une recherche dans une structure de données, une comparaison est une opération dominante, notée O() et prononcée « big-Oh » ou « Oh ».
Il existe de nombreux algorithmes de recherche dans une structure de données tels que la recherche linéaire, la recherche binaire, la recherche par interpolation, la recherche par saut, la recherche exponentielle, la recherche de Fibonacci, la recherche de sous-liste, la recherche binaire omniprésente, la recherche binaire illimitée, la fonction récursive pour la recherche de sous-chaînes et le programme récursif. pour rechercher un élément linéairement dans le tableau donné. L'article se limite aux algorithmes de recherche linéaires et binaires et à leurs principes de fonctionnement.
Voyons en détail la recherche linéaire et la recherche binaire dans la structure de données.
Recherche linéaire
L'algorithme de recherche linéaire recherche séquentiellement tous les éléments du tableau. Son meilleur temps d'exécution est un, tandis que le pire temps d'exécution est n, où n est le nombre total d'éléments dans le tableau de recherche.
C'est l'algorithme de recherche le plus simple dans la structure de données et vérifie chaque élément de l'ensemble d'éléments jusqu'à ce qu'il corresponde à l'élément de recherche jusqu'à la fin de la collecte de données. Lorsque les données ne sont pas triées, un algorithme de recherche linéaire est préféré.
La recherche linéaire présente certaines complexités, comme indiqué ci-dessous :
- Complexité spatiale
La complexité de l'espace pour la recherche linéaire est O(n) car elle n'utilise aucun espace supplémentaire où n est le nombre d'éléments dans un tableau.
- Complexité temporelle
*La complexité dans le meilleur des cas = O(1) se produit lorsque l'élément de recherche est présent au niveau du premier élément du tableau de recherche.
*La complexité dans le pire des cas = O(n) se produit lorsque l'élément de recherche n'est pas présent dans l'ensemble d'éléments ou le tableau.
*La complexité moyenne = O(n) est mentionnée lorsque l'élément est présent quelque part dans le tableau de recherche.
Exemple,
Prenons un tableau d'éléments comme indiqué ci-dessous:
45, 78, 12, 67, 08, 51, 39, 26
Pour trouver '51' dans un tableau de 8 éléments donné ci-dessus, un algorithme de recherche linéaire vérifiera chaque élément séquentiellement jusqu'à ce que son pointeur pointe vers 51 dans l'espace mémoire. Il faut un temps O(6) pour trouver 51 dans un tableau. Pour trouver 12, dans le tableau ci-dessus, il faut O(3), alors que, pour 26, il faut O(8) temps.
Recherche binaire
Cet algorithme trouve des éléments spécifiques en comparant les éléments les plus médians de la collecte de données. Lorsqu'une correspondance se produit, elle renvoie l'index de l'élément. Lorsque l'élément du milieu est supérieur à l'élément, il recherche un élément central du sous-tableau de gauche. En revanche, si l'élément du milieu est plus petit que l'élément de recherche, il explore le milieu de l'élément dans le sous-tableau de droite. Il continue à rechercher un élément jusqu'à ce qu'il le trouve ou jusqu'à ce que la taille des sous-tableaux devienne nulle.
La recherche binaire nécessite un ordre trié des éléments. C'est plus rapide qu'un algorithme de recherche linéaire. Il fonctionne sur le principe de diviser pour régner.
Complexité d'exécution = O(log n)
L'algorithme de recherche binaire a des complexités comme indiqué ci-dessous :
- Complexité du pire cas = O (n log n)
- Complexité moyenne = O (n log n)
- Complexité du meilleur cas = O (1)
Exemple,
Prenons un algorithme trié de 08 éléments :
08, 12, 26, 39, 45, 51, 67, 78
Pour trouver 51 dans un tableau des éléments ci-dessus,
L'algorithme divisera un tableau en deux tableaux, 08, 12, 26, 39 et 45, 51, 67, 78
Comme 51 est supérieur à 39, il commencera à rechercher des éléments sur le côté droit du tableau.
Il divisera en outre le en deux tels que 45, 51 et 67, 78
Comme 51 est plus petit que 67, il commencera à chercher à gauche de ce sous-tableau.
Ce sous-réseau est à nouveau divisé en deux en 45 et 51.
Comme 51 est le nombre correspondant à l'élément de recherche, il renverra son numéro d'index de cet élément dans le tableau.
Il conclura que l'élément de recherche 51 est situé à la 6ème position dans un tableau.
La recherche binaire réduit le temps de moitié car le nombre de comparaisons est considérablement réduit par rapport à l'algorithme de recherche linéaire.
Lire : Types de structures de données en Python
Recherche d'interpolation
Il s'agit d'une variante améliorée de l'algorithme de recherche binaire et fonctionne sur la position de sondage de l'élément de recherche. Semblable aux algorithmes de recherche binaires, il ne fonctionne efficacement que sur la collecte de données triées.
Pire temps d'exécution = O(n)
Lorsque l'emplacement de l'élément cible est connu dans la collecte de données, une recherche par interpolation est utilisée. Pour trouver un numéro dans l'annuaire téléphonique, si l'on veut rechercher le numéro de téléphone de Monica, au lieu d'utiliser la recherche linéaire ou binaire, on peut directement sonder le stockage de l'espace mémoire où les noms commencent par 'M'.
Conclusion
La recherche dans les structures de données consiste à trouver un élément donné dans le tableau de 'n' éléments. Il existe deux catégories, à savoir. Recherche séquentielle et recherche par intervalle dans la recherche. Presque tous les algorithmes de recherche sont basés sur l'une de ces deux catégories. Les recherches linéaires et binaires sont les deux algorithmes simples et faciles à mettre en œuvre dans lesquels le binaire fonctionne plus rapidement que les algorithmes linéaires.
Bien que la recherche linéaire soit la plus simple, elle vérifie chaque élément jusqu'à ce qu'elle trouve une correspondance avec l'élément de recherche, donc efficace lorsque la collecte de données n'est pas triée correctement. Mais, si la collecte de données est triée et que la longueur d'un tableau est considérable, la recherche binaire est plus rapide.
La structure des données est une partie essentielle de la programmation informatique tout en traitant des ensembles de données. Les programmeurs et les développeurs doivent continuer à se mettre à jour et à se perfectionner avec les bases et les mises à jour des techniques de programmation informatique. Les programmeurs traitant de la structure des données devraient opter souvent pour des cours.
Si vous êtes curieux d'en savoir plus sur la science des données, consultez le programme Executive PG en science des données de IIIT-B & upGrad qui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques, un mentorat avec des experts de l'industrie, 1-on-1 avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.
