introduction searching algorithms c
Vue d'ensemble des algorithmes de recherche en C ++.
Nous cherchons toujours quelque chose ou l'autre dans notre vie de tous les jours. Tout comme dans notre vie de tous les jours, en tant que professionnel du logiciel, nous devons rechercher des informations sur notre ordinateur. La recherche d'informations doit être effectuée rapidement car nous ne pouvons pas nous permettre de perdre beaucoup de temps à rechercher des informations.
Par conséquent, nous avons besoin de techniques de recherche efficaces ou d'algorithmes capables de rechercher une information donnée en peu de temps et de la donner à l'utilisateur afin que l'utilisateur puisse poursuivre les autres tâches.
=> Visitez ici pour la liste complète des didacticiels C ++.
Ce que vous apprendrez:
Techniques de recherche
Nous avons deux principales techniques de recherche qui sont principalement utilisées pour rechercher des informations.
Ceux-ci inclus:
- Recherche linéaire
- Recherche binaire
Dans ce didacticiel, nous allons explorer ces deux techniques de recherche en détail.
Recherche linéaire
Il s'agit de la technique de recherche la plus élémentaire et elle est également plus facile à mettre en œuvre. Dans une recherche linéaire, la clé à rechercher est comparée linéairement avec chaque élément de la collection de données. Cette technique fonctionne efficacement sur les structures de données linéaires.
Considérons le tableau suivant.
Ci-dessus, le tableau de sept éléments. Si nous voulons rechercher clé = 23, alors à partir du 0eélément, la valeur de la clé sera comparée à chaque élément. Une fois que l'élément clé correspond à l'élément du tableau, cet emplacement particulier sera renvoyé. Dans ce cas, l'emplacement, 4 sera renvoyé car la valeur-clé correspond à la valeur à cet emplacement.
Nous avons implémenté une recherche linéaire en utilisant le langage C ++ et Java ci-dessous.
Implémentation C ++
#include #include using namespace std; int main() { int myarray(10) = {21,43,23,54,75,13,5,8,25,10}; int key,loc; cout<<'The input array is'<key; for (int i = 0; i<10; i++) { if(myarray(i) == key) { loc = i+1; break; } else loc = 0; } if(loc != 0) { cout<<'Key found at position '< Production:
générateur de nombres aléatoires 0-1
Le tableau d'entrée est
21 43 23 54 75 13 5 8 25 10
Entrez la clé à rechercher: 3
Impossible de trouver la clé donnée dans le tableau
Le tableau d'entrée est
21 43 23 54 75 13 5 8 25 10
Entrez la clé à rechercher: 75
Clé trouvée en position 5 dans le tableau
Implémentation Java
import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main(String() args) { int() myarray = {21,43,23,54,75,13,5,8,25,10}; int key,location=0; Scanner sc = new Scanner(System.in); System.out.println('The input array is'); for(int i=0;i<10;i++){ System.out.print(myarray(i)+' '); } System.out.println('
'); System.out.println('Enter key'); key = sc.nextInt(); for(int i = 0; i<10; i++) { if(myarray(i)==key) { location = i+1; break; } else location = 0; } if(location != 0) { System.out.println('key found at location ' + location); } else System.out.println('Key not found'); } } Production:
Le tableau d'entrée est
21 43 23 54 75 13 5 8 25 10
La touche Entrée
2. 3
clé trouvée à l'emplacement 3
quel est le but des tests de régression
La recherche linéaire peut être effectuée sur toute structure de données linéaire ayant des éléments triés ou non triés. Mais cela prend plus de temps s'il y a trop d'éléments et si l'élément clé est vers la fin car chaque élément est comparé à la valeur clé.
Recherche binaire
La recherche binaire est une technique qui utilise la technique «diviser et conquérir» pour rechercher une clé. Il fonctionne sur une liste linéaire triée d'éléments. La liste triée est la condition de base pour qu'une recherche binaire fonctionne.
Dans la méthode de recherche binaire, la liste est divisée en deux à plusieurs reprises et l'élément clé est recherché dans les deux moitiés de la liste jusqu'à ce que la clé soit trouvée.
Par exemple,prenons le tableau trié suivant de 10 éléments.
Disons que la clé = 21 doit être recherchée dans le tableau.
Calculons l'emplacement du milieu du tableau.
Milieu = 0 + 9/2 = 4
Par exemple,prenons le tableau trié suivant de 10 éléments.
Clé = 21
Tout d'abord, nous comparerons la valeur clé avec l'élément (mid). Nous trouvons que la valeur de l'élément à mi = 21.
Ainsi, nous trouvons que key = (mid). D'où la clé est trouvée.
clé = 25
Nous comparons d'abord la valeur clé à mid. Alors (21<25), we will directly search for the key in the upper half of the array.
comment ouvrir un .torrent
Maintenant, nous trouverons à nouveau le milieu de la moitié supérieure du tableau.
Milieu = 4 + 9/2 = 6
La valeur à l'emplacement (mid) = 25
Maintenant, nous comparons l'élément clé avec l'élément central. Donc (25 == 25), nous avons donc trouvé la clé à l'emplacement (milieu).
Nous divisons le tableau à plusieurs reprises et en comparant l'élément clé avec le milieu, nous décidons dans quelle moitié rechercher la clé.
Vous trouverez ci-dessous l'implémentation C ++ et Java pour la recherche binaire.
Implémentation C ++
#include #include using namespace std; int binarySearch(int myarray(), int beg, int end, int key) { int mid; if(end >= beg) { mid = (beg + end)/2; if(myarray(mid) == key) { return mid+1; } else if(myarray(mid) key; location = binarySearch(myarray, 0, 9, key); if(location != -1) { cout<<'Key found at location '< Production:
Le tableau d'entrée est
5 8 10 13 21 23 25 43 54 75
Entrez la clé à rechercher: 21
Clé trouvée à l'emplacement 5
Implémentation Java
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main(String() args) { int() myarray = {5,8,10,13,21,23,25,43,54,75}; int key, location = -1; System.out.println('The input array is'); for(int i=0;i= beg) { mid = (beg + end)/2; if(myarray(mid) == key) { return mid+1; } else if(myarray(mid) Production:
Le tableau d'entrée est
5 8 10 13 21 23 25 43 54 75
Entrez la clé à rechercher
vingt et un
l'emplacement de la clé est 5
La recherche binaire est plus efficace en termes de temps et d'exactitude. La technique de recherche linéaire est rarement utilisée car elle est plus lourde et plus lente. La recherche binaire est beaucoup plus rapide par rapport à une recherche linéaire.
Conclusion
Les techniques de recherche nous aident à rechercher des informations stockées sur un ordinateur afin que l'utilisateur puisse procéder aux autres tâches de traitement de l'information. La technique de recherche linéaire est simple et plus facile mais n'est pas largement utilisée.
La technique de recherche binaire est beaucoup plus rapide et efficace et est donc largement utilisée.
Dans notre prochain tutoriel, nous explorerons en détail les différentes techniques de tri.
=> Consultez le guide de formation Perfect C ++ ici.
lecture recommandée
- Introduction au langage de programmation Java - Tutoriel vidéo
- Introduction à Appium Studio: avantages et fonctionnalités clés
- Algorithmes dans STL
- Meilleure série de tutoriels C # GRATUITS: Le guide ultime de C # pour les débutants
- JMeter Video 1: Introduction, téléchargement et installation de JMeter
- Processus d'introduction et d'installation de Python
- Qu'est-ce qu'Unix: une brève introduction à Unix
- Introduction à Micro Focus LoadRunner - Test de charge avec LoadRunner Tutorial # 1
