Suchen Sie mit C++ wiederholt nach einem Element, indem Sie das Element nach jeder erfolgreichen Suche verdoppeln

In diesem Artikel erhalten wir ein Array von Ganzzahlen und ein Schlüsselwort. Wir müssen wiederholt nach dem Schlüssel im Array suchen und ihn bei jedem Suchvorgang verdoppeln. Wir müssen einen Wert zurückgeben, der zum Zeitpunkt dieser Operation nicht im Array vorhanden ist.

Schauen Sie sich einige Eingabeszenarien an, um zu sehen, wie die Methode in verschiedenen Situationen funktioniert

Schauen wir uns ein Array [1,2,6,3,7,4,9] an, dessen Schlüssel 1 ist.

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

Wenn wir 1 finden, verdoppeln wir es auf 2.

Wenn wir 2 finden, verdoppeln wir es auf 4.

Wenn wir 4 finden, verdoppeln wir es auf 8.

Wir geben 8 zurück, da das Array kein Element 8 enthält

In einem anderen Fall betrachten wir ein Array {2, 3, 7, 8, 5, 9}, dessen Schlüssel 1 ist.

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

Wir geben 1 unverändert zurück, da im Eingabearray kein Element 1 vorhanden ist.

Algorithmus

• Sortieren Sie die Array-Elemente, da die Komplexität der Durchführung einer binären Suche bei kleinen Arrays gering ist.

• Immer wenn ein Element im Array mit einem Schlüsselwert übereinstimmt, verdoppeln Sie den Schlüsselwert und durchsuchen Sie das Array erneut, um ein Element zu finden, das mit dem neuen Schlüssel übereinstimmt.

• Wiederholen Sie diesen Schritt, bis im Array keine Elemente mehr vorhanden sind, die dem Doppelschlüsselwert entsprechen.

• Der endgültige Schlüsselwert ist die erhaltene Ausgabe.

Beispiel (mit Vektor-ADT)

Wir beginnen mit der Implementierung dieser Methode, indem wir das Array sortieren. Danach machen wir genau das, was in der Frage steht; suchen und verdoppeln. Wir führen eine optimierte Suche durch binäre Suche durch. Schauen wir uns ein C++-Programm an, indem wir dieselbe Logik anwenden -

#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;
}

Ausgabe

8

Beispiel (ohne Vektor-ADT)

C++-Programme folgen ebenfalls der gleichen Logik, verwenden jedoch nicht den abstrakten Vektordatentyp.

Wir beginnen mit der Umsetzung dieses Ansatzes, indem wir das Array sortieren. Danach machen wir, was in der Frage verlangt wird: Suchen und verdoppeln. Wir optimieren mittels binärer Suche.

#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;
}

Ausgabe

12

Fazit

Wir verwenden die binäre STL-Suchmethode, um je nachdem, ob das Element gefunden wird, wahr oder falsch zurückzugeben. Wir können auch unsere benutzerdefinierte binäre Suchimplementierung verwenden. STL bietet hervorragende Sortier- und Suchmethoden, die uns helfen, Probleme zu schreiben, ohne die Implementierung zu überdenken.

Das obige ist der detaillierte Inhalt vonSuchen Sie mit C++ wiederholt nach einem Element, indem Sie das Element nach jeder erfolgreichen Suche verdoppeln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!