Explication des algorithmes de recherche linéaire et binaire
La capacité de rechercher certaines informations est un aspect vital de la technologie informatique. Les formules de recherche sont utilisées pour rechercher un produit spécifique dans une collection de données.
Les algorithmes renvoient un résultat booléen (réel ou faux) à une requête de recherche. Ils peuvent également être modifiés pour fournir la position du membre de la famille de la valeur trouvée.
Pour ce court article, les algorithmes se concentreront sur la détermination de l’existence d’une valeur.
Algorithmes de recherche linéaire
La recherche linéaire est également appelée recherche séquentielle. Dans ce type de recherche, chaque valeur d’une liste est recherchée une par une de manière ordonnée tout en vérifiant si la valeur recherchée existe.
L’algorithme vérifie la valeur par valeur jusqu’à ce qu’il découvre la valeur que vous recherchez ou qu’il manque des valeurs à rechercher. Lorsqu’il n’y a plus de valeurs à parcourir, cela signifie que votre question de recherche n’existe pas dans la liste.
Un algorithme de recherche séquentielle prend en compte une liste de contrôle de valeurs et la chose souhaitée dans la liste comme ses spécifications. Le résultat de retour est initialisé comme Faux ainsi que va certainement changer pour Vrai lorsque la valeur préférée est localisée.
Voir l’implémentation Python ci-dessous à titre d’exemple :
Analyse d’algorithme
La meilleure situation se produit lorsque la chose préférée est la première sur la liste de contrôle. La pire situation se produit lorsque le produit souhaité est le dernier sur la liste de contrôle (le nième élément). Par conséquent, la complexité temporelle de la recherche linéaire est O(n).
La circonstance d’instance ordinaire dans l’algorithme ci-dessus est n/2.
Recherche linéaire modifiée
Il est essentiel de comprendre que l’algorithme utilisé pense qu’une liste arbitraire de choses lui est donnée. C’est-à-dire que les choses de la liste de contrôle ne restent pas dans un ordre certain.
Supposons que les produits soient dans un certain ordre, du plus petit au plus grand. Il serait possible d’obtenir un certain avantage dans le calcul.
Prenons un exemple d’essayer de trouver 19 dans la liste donnée :. Après avoir atteint 23, il deviendrait certainement clair que la chose que l’on essaie de trouver n’existe pas dans la liste. Par conséquent, il ne serait plus important de continuer à rechercher le reste des produits de la liste.
Algorithmes de recherche binaire
Vous avez en fait vu exactement comment une liste ordonnée peut minimiser le calcul requis. L’algorithme de recherche binaire profite encore plus de cette efficacité que le fait d’avoir une liste ordonnée présente.
La formule commence par prendre une valeur centrale d’une liste de contrôle achetée et par vérifier si c’est la valeur souhaitée. Si ce n’est pas le cas, la valeur est examinée si elle est inférieure ou supérieure à la valeur souhaitée.
Si c’est moins, il n’est pas nécessaire d’examiner les cinquante pour cent inférieurs de la liste. Sinon, s’il est supérieur, il passe ensuite à la moitié supérieure de la liste.
Quelle que soit la sous-liste (gauche ou droite) choisie, la valeur médiane sera à nouveau établie. La valeur est à nouveau examinée si c’est la valeur requise. Si ce n’est pas le cas, on vérifie si c’est inférieur ou supérieur à la valeur demandée.
Ce processus est répété jusqu’à ce qu’une valeur soit découverte si elle est là.
L’exécution Python répertoriée ci-dessous concerne la formule de recherche binaire.
def recherchebinaire( maliste, produit):
Analyse d’algorithme
Le meilleur scénario se produit lorsque le produit recherché est découvert comme étant l’article du milieu. La pire des circonstances n’est cependant pas aussi simple. Se conformer à l’évaluation ci-dessous :
Après le tout premier contraste, il restera certainement n/2 choses. Après le 2ème, il restera n/4 choses. Après le 3, n/8.
Notez que le nombre de produits continue de diminuer de moitié jusqu’à ce qu’ils atteignent n/2i où i est la variété des comparaisons. Après tout le fractionnement, nous nous retrouvons avec un seul élément.
Cela implique:
n/ 2i= 1 Par conséquent, la recherche binaire est O( log n).
Passer au tri
Dans la recherche binaire, nous avons considéré une situation où la variété fournie était déjà obtenue. Cependant, cela signifie que vous aviez un ensemble de données non ordonné et que vous souhaitiez également effectuer une recherche binaire dessus. Qu’est-ce que tu ferais?
La réponse est simple : aimons-le. Il existe un certain nombre de stratégies d’organisation en informatique qui ont fait l’objet de recherches approfondies. Parmi ces méthodes, vous pouvez commencer à examiner la formule de tri par sélection, tandis que nous avons également obtenu de nombreux guides associés à divers autres emplacements.
