C++-Programm zum Suchen nach Elementen in einem sortierten und gedrehten Array

Wir erhalten ein sortiertes Array, das um einen Punkt gedreht ist. Wir erhalten auch einen Schlüssel zum Durchsuchen des Arrays. Die zum Suchen nach Elementen in diesem gedrehten Array verwendete Logik ist -

• Zuerst finden wir das mittlere Element des Arrays. Wenn der Schlüssel vorhanden ist, geben wir zurück, dass der Schlüssel im Array vorhanden ist.

• Wenn sich der Schlüssel nicht in der Mitte befindet, können wir sehen, ob der linke Teil des Arrays (von links nach Mitte) sortiert ist. Wenn es sortiert ist, können Sie links nach dem Schlüssel suchen, andernfalls können Sie rechts (Mitte+1, rechts) nach dem Schlüssel suchen

• Wenn der Schlüssel nicht in der Mitte gefunden wird und der linke Teil nicht sortiert ist, sortieren wir den rechten Teil und können dann sehen, ob der Schlüssel im rechten Teil vorhanden ist, oder wir suchen auf der linken Seite das Array im rechten Teil

• Sonst kehren wir nicht gefunden zurück.

Sehen wir uns unten einige Eingabe- und Ausgabeszenarien an -

Stellen Sie sich vor, es gibt ein Array, das aus seinen Elementen besteht. Beispiel: 2, 5, 7, 9, 11 werden nach der Drehung zu 5, 9, 11, 2, 7. Angenommen, der Array-Schlüssel ist 2.

Input: arr[] = {5, 9, 11, 2, 7}, Key=2
Output: Element "2" found at 3rd index

Nehmen wir ein anderes Szenario an, in dem sich der Schlüssel nicht im angegebenen Array befindet.

Input: arr[] = {10, 23, 45, 77, 84}, Key=90
Output: Element "90" not found.

Algorithmus

Die folgenden Schritte zeigen, wie Sie es erreichen.

• Finden Sie das mittlere Element eines Arrays.

• Teilen Sie das Array in zwei Teile. (Mitte = links + rechts) / 2

• Überprüfen Sie, ob der Schlüssel ein mittleres Element ist.

• Andernfalls prüft das Element auf der linken Seite des Arrays und es ist sortiert

• Andernfalls überprüfen Sie das richtige Element (Mitte+1, rechts)

• Andernfalls sortieren Sie den linken Teil und überprüfen Sie

• Andernfalls wird das nicht gefundene Element zurückgegeben.

Beispiel

Angenommen, wir haben ein Array „2,3,4,5,6,7,8“ und das gedrehte Array ist „5,6,7,8,2,3,4“. Der Schlüssel dieses Arrays ist 2.

Die C++-Implementierung dieser Operation lautet wie folgt -

#include <iostream>
#include <vector>
using namespace std;
bool solve(vector<int> arr, int left, int right, int key) {
   if (left > right) {
      return false;
   }
   int mid = (left + right)/2;
   if (arr[mid] == key) {
      return true;
   }
   if (arr[left] <= arr[mid]) {
      if (key >= arr[left] && key <= arr[mid]) {
         return solve(arr, left, mid-1, key);
      }
      return solve(arr, mid+1, right, key);
   }
   if (key >= arr[mid] && key <= arr[right])
      return solve(arr, mid+1, right, key);
   return solve(arr, left, mid-1, key);
}
int main() {
   vector<int> arr = {5, 6, 7, 8, 2, 3, 4};
   int key = 2;
   if(solve(arr, 0, arr.size()-1, key)) cout << key << " is present";
      else cout << key << " is not present";
   return 0;
}

Ausgabe

2 is present

Fazit

Eine andere Möglichkeit, dieses Problem zu lösen, besteht darin, den Drehpunkt oder Index der Array-Rotation zu finden und dann eine binäre Suche an den Kanten durchzuführen. Unsere Methode erfordert nur eine binäre Suche, um das Problem zu lösen. Wann immer wir das Suchen und Sortieren von Arrays sehen, sollten wir die binäre Suche als eine der Suchmethoden in Betracht ziehen.

Das obige ist der detaillierte Inhalt vonC++-Programm zum Suchen nach Elementen in einem sortierten und gedrehten Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!