En utilisant C++, recherchez un élément à plusieurs reprises en doublant l'élément après chaque recherche réussie

Dans cet article, on nous donne un tableau d'entiers et un mot-clé. Nous devons rechercher à plusieurs reprises la clé dans le tableau, en la doublant à chaque recherche. Nous devons renvoyer une valeur qui n'est pas présente dans le tableau au moment de cette opération.

Examinez quelques scénarios de saisie pour voir comment la méthode fonctionne dans différentes situations

Regardons un tableau [1,2,6,3,7,4,9] dont la clé est 1.

Input: {1, 2, 3, 4, 5, 6}, k = 1
Result: 8

Si on trouve 1, on le double à 2.

Si on en trouve 2, on le double à 4.

Si on en trouve 4, on le double à 8.

Nous renvoyons 8 car il n'y a pas d'élément 8 dans le tableau

Dans un autre cas, on considère un tableau {2, 3, 7, 8, 5, 9} dont la clé est 1.

Input: {2, 3, 7, 8, 5, 9}, k = 1
Result: 1

Nous renvoyons 1 tel quel car il n'y a pas d'élément 1 dans le tableau d'entrée.

Algorithme

• Triez les éléments du tableau car la complexité d'effectuer une recherche binaire est faible pour les petits tableaux.

• Chaque fois qu'un élément du tableau correspond à une valeur clé, doublez la valeur clé et recherchez à nouveau le tableau pour trouver un élément correspondant à la nouvelle clé.

• Répétez cette étape jusqu'à ce qu'il n'y ait plus d'éléments correspondant à la valeur de la double clé dans le tableau.

• La valeur clé finale est le résultat obtenu.

Exemple (en utilisant le vecteur ADT)

Nous commençons à implémenter cette méthode en triant le tableau. Après cela, nous ferons exactement ce que dit la question : rechercher et doubler. Nous effectuons une recherche optimisée via une recherche binaire. Regardons un programme C++ en appliquant la même logique -

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int solve(vector<int>& arr, int key) {
   sort(arr.begin(), arr.end());
   bool found = binary_search(arr.begin(), arr.end(), key);
   while(found) {
      key*=2;
      found = binary_search(arr.begin(), arr.end(), key);
   }
   return key;
}
int main() {
   vector<int> arr = {1,2,6,3,7,4,9};
   int key = 1;
   cout << solve(arr, key) << endl;
   return 0;
}

Sortie

8

Exemple (sans vecteur ADT)

Les programmes C++ suivent également la même logique mais n'utilisent pas le type de données vectoriel abstrait.

Nous commençons à mettre en œuvre cette approche en triant le tableau. Après cela, nous ferons ce que demande la question : rechercher et doubler. Nous optimisons via la recherche binaire.

#include <bits/stdc++.h>
using namespace std;
int SearchElement(int arr[], int n, int k) {

   // Sorting is done so binary searching in the element
   // would be easier
   sort(arr, arr + n);
   int max = arr[n - 1]; // Declaring the maximum element in the array
   while (k < max) {

      // search for the element k in the array
      if (binary_search(arr, arr + n, k))
         k *= 2;
      else
      return k;
   }
   return k;
}
int main() {
   int arr[] = {1,2,6,3,7,4,9};
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   cout << SearchElement(arr, n, k);
   return 0;
}

Sortie

12

Conclusion

Nous utilisons la méthode de recherche binaire STL pour renvoyer vrai ou faux selon que l'élément est trouvé. Nous pouvons également utiliser notre implémentation de recherche binaire personnalisée. STL fournit d'excellentes méthodes de tri et de recherche, qui nous aident à rédiger des problèmes sans trop réfléchir à l'implémentation.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!