Recherche binaire C ++
Après avoir ouvert le shell terminal rapidement, vous devez avoir besoin d'un fichier C ++ pour y créer votre code de recherche binaire. Par conséquent, une commande simple mot-clé en un mot, je.e., «Touch» sera utilisé pour cette raison. Nous l'avons donc utilisé pour créer un fichier C ++ nommé «binaire.CC ”et l'ouvrir via l'éditeur GNU Nano intégré qui propose la configuration de l'ubuntu 20.04 Système. Les deux commandes ont déjà été démontrées à l'aide de l'image ci-dessous.
Exemple 01: méthode itérative
La toute première méthode que nous avons utilisée ici est la méthode itérative de la recherche binaire. Ce serait assez simple à faire. Une fois le fichier ouvert dans l'éditeur Nano, nous avons ajouté les fichiers d'en-tête nécessaires pour que le code s'exécute. L'espace de noms qui doit être standard est nécessaire pour le code C ++ ici. Une fonction définie par l'utilisateur nommé «Search» a été créée pour effectuer une recherche binaire. Cette fonction définie par l'utilisateur prend 4 arguments dans ses paramètres, i.e., «A []» pour le tableau, gauche pour les tableaux gauche la plus valeur, droite pour les tableaux à droite, et V pour que la valeur soit recherchée dans le tableau «A».
Dans le début de cette fonction, nous avons utilisé une simple boucle «while» pour vérifier si la valeur la plus à gauche ou la première du tableau est inférieure ou égale à la valeur la plus droite (entrée enfin) du tableau ou non. Si la valeur est inférieure ou égale à la valeur la plus élevée, elle créera un nouveau point dans le tableau, je.e., milieu. Ce point médian a été calculé en utilisant à la gauche et à la droite. Une fois le point médian trouvé, nous utilisons l'instruction «IF» pour vérifier si la valeur à l'index moyen d'un tableau «A» est la même que la valeur demandée à vérifier, i.e., "V". Si la condition devenait efficace et que la valeur «V» correspondait à la valeur de l'indice à mi-index, elle renverra l'index mi-index d'un tableau. Au début, notre tableau a deux moitiés, à gauche et à droite. Celui gauche contient des valeurs plus petites, tandis que celle de droite contient les valeurs plus grandes par rapport à la valeur de l'index moyen. Lorsque la valeur à un point médian est inférieure à la valeur à rechercher, nous n'avons pas besoin de considérer la moitié gauche d'un tableau car cela contiendra des valeurs plus petites.
Ainsi, nous mettrons à jour notre variable gauche avec l'index de «Mid + 1». D'un autre côté, si la valeur intermédiaire est supérieure à la valeur demandée à vérifier, alors nous devons ignorer la moitié droite (valeurs plus grandes) d'un tableau. Ainsi, la bonne variable sera mise à jour par une nouvelle valeur, je.e., "Mid-1". Ce processus continuera de faire jusqu'à ce que la gauche d'un tableau soit égale ou inférieure au bon point d'un tableau. Si non des conditions ne sont remplies, nous n'avons pas trouvé la valeur dans le tableau et le retour à -1 comme index à la méthode principale.
Maintenant, est venu à l'implémentation de la fonction principale (). Dans cette fonction, nous avons déclaré un tableau nommé «A» avec certaines valeurs entières. Le tableau est déjà trié par ordre croissant. Alors une variable «V» a été initialisée dans laquelle une valeur saisie par un utilisateur sera enregistrée. L'instruction COUT indique à un utilisateur de saisir un certain nombre tandis que l'instruction CIN est utilisée pour collecter l'entrée de l'utilisateur et l'enregistrer dans la variable «V».
Une autre variable, «N» a été définie pour obtenir la taille totale d'un tableau avec une utilisation de la fonction sizeof () sur le tableau «A». Une autre variable, «Val» a été utilisé pour obtenir l'index de la méthode de recherche comme une valeur de retour en l'appelant. L'appel de fonction passe le tableau A, point gauche comme 0, point droit comme entier «n-1», et la valeur «v» à rechercher. Si la méthode de recherche renvoie «-1» à la variable «Val», la première instruction COUT sera exécutée; Sinon, le second sera exécuté et affichera l'index d'une valeur correspondante.
Ainsi, le code nécessite d'abord la compilation. Après la première et la deuxième exécution, l'utilisateur est entré 14 et 19, et il a été égalé avec l'index 3 et 8, respectivement, comme affiché. Lors de la troisième exécution, cela n'a pas fonctionné comme indiqué. Donc, le compilateur G ++ est là pour votre aide.
Exemple 02: méthode récursive
Il s'agissait de la méthode itérative de la recherche binaire en C++. Ayons une deuxième méthode pour effectuer une recherche binaire en C ++, une méthode connue et récursive. La méthode récursive serait la même que la méthode itérative mais appelle de manière récursive sa méthode de recherche binaire. Nous l'expliquerons avec le code. Alors, ouvrez le même fichier et mettez à jour la méthode de recherche. Nous avons utilisé la même boucle dans la méthode de recherche avec les mêmes conditions, i.e., Instructions IF-ELSE, instruction IF unique et calcul du milieu.
Le seul changement a été effectué dans l'instruction if-else de la fonction de recherche. Lorsque la valeur du point médian est supérieure à la valeur à rechercher dans la méthode de recherche et que la condition est satisfaite, il appellera la même méthode de recherche avec peu de changement dans ses paramètres. Tous les paramètres seront les mêmes, sauf la «bonne» valeur ponctuelle, qui est maintenant l'indice «Mid-1». D'un autre côté, lorsqu'une valeur médiane est inférieure à la valeur à rechercher, je.e., «V» et la condition n'est pas satisfaite, elle appellera la même fonction avec un petit changement à son argument de paramètre «à gauche». Le point de gauche sera mis à jour avec l'index de «Mid + 1» maintenant.
Vous pouvez voir que la fonction principale () est 100% la même que l'exemple itératif ci-dessus, et il n'a pas un seul changement de caractère.
Tout d'abord, compilez ce code récursif mis à jour avec G ++, puis exécutez-le. Après la première exécution, il renvoie 3 en conséquence à la valeur 14, alors qu'aucun index n'a été trouvé jusqu'à présent pour la valeur 24 après la deuxième exécution.
Conclusion:
L'article entier ci-dessus concerne la recherche binaire en C++. La recherche binaire a été découverte et bien expliquée avec deux méthodes différentes, je.e., itératif et récursif. Tous les exemples mis en œuvre et démontrés sont assez simples à faire et faciles à comprendre, car chaque étape a été expliquée assez brièvement. Par conséquent, nous espérons que cet article serait tout aussi bénéfique pour un utilisateur naïf, nouveau et expert.