Suche vorwärts und rückwärts im unsortierten Array

Unsortiertes Array – Ein Array ist eine Datenstruktur, die aus einer Sammlung von Elementen desselben Typs besteht. Ein unsortiertes Array ist eine Struktur, in der die Reihenfolge der Elemente zufällig ist, d. h. beim Einfügen wird das Element unabhängig von der Reihenfolge der vorherigen Elemente zum letzten Element hinzugefügt und die Suche in einem solchen Array leidet nicht unter der Hilfe von Suchalgorithmen Fehlen eines Musters für die Elementpositionierung.

Suchen – Suchen in einem Array bedeutet, nach einem bestimmten Element im Array zu suchen, das die Position des gewünschten Elements oder eine Bool-Anweisung zurückgeben kann, die angibt, ob das Element im Array vorhanden ist oder nicht.

• Vorwärtssuche – Die Vorwärtssuche in einem Array bedeutet, dass eine lineare Suchdurchquerung des Arrays beginnend mit dem 0. Index (d. h. dem ersten Element) durchgeführt wird.

• Umgekehrte Suche – Das Durchsuchen eines Arrays in umgekehrter Reihenfolge bedeutet, dass das Array ausgehend vom (n-1)-ten Index (d. h. dem letzten Element) linear durchsucht wird.

Problemstellung

Stellen Sie bei einem gegebenen Suchelement x fest, ob x im folgenden Fall existiert -

• Arrays mit Elementen gleicher Größe, Arrays aus ganzen Zahlen.

• Arrays mit Elementen unterschiedlicher Größe, Arrays aus Strings.

Beispiel 1

Input: x = 4, [6, 1, 4, 10, 2]

Output: TRUE

Erklärung – Im angegebenen Array erscheint 4 am zweiten Index.

Beispiel 2

Input: x = “high”, [“goat”, “ice”, “hgh”]

Output: False

Erläuterung – Im angegebenen Array existiert „high“ nicht.

Lösung

Wie oben erwähnt, beginnt die Vorwärtssuche beim ersten Element und die Rückwärtssuche beim letzten Element. Durch die Kombination dieser beiden Methoden kann die Zeit für die Suche nach einem Element im Array um das Doppelte reduziert werden, da die erste und zweite Hälfte des Arrays gleichzeitig überprüft werden.

Um herauszufinden, ob ein Element in einem Array vorkommt, definieren Sie „first“ und „last“ als erstes und letztes Element des Arrays. Gibt „true“ zurück, wenn entweder das erste oder das letzte Element das erforderliche Element ist. Andernfalls wird das erste Element um 1 erhöht, das letzte Element um 1 verringert und so lange fortgesetzt, bis das Element gefunden wird. Wenn „first“ und „last“ nach Abschluss des Durchlaufs gleich sind, wird „false“ zurückgegeben, wenn das Element nicht gefunden wird.

Pseudocode

procedure frontBack (arr[], x)
   first = 0
   last = n - 1
   while first <= last
      If arr[first] == x or arr[last] == x
         ans = true
       end if
      front = front + 1
      last = last - 1
   ans = false
end procedure

Beispiel: C++-Implementierung

Im folgenden Programm nehmen wir den ersten Fall eines Arrays von Ganzzahlen. Rufen Sie die erste und die nächste Variable ab, während Sie das erste und das letzte Element überprüfen, um das erforderliche Element zu finden. Wenn das Element gefunden wird, geben Sie „true“ zurück, andernfalls gehen Sie zum nächsten Element und überprüfen Sie es erneut.

#include <bits/stdc++.h>
using namespace std;
// Function to front back search an element in the array
bool frontBack(int arr[], int x){
   int first = 0, last = 9;
   
   // loop execute till the element is found or traversal completes
   while (first <= last){
      if (arr[first] == x || arr[last] == x){
         return true;
      }
      first++;  // Incrementing first
      last--;  // Decrementing last
   }
   return false;
}
int main(){
   int arr[10] = {21, 43, 10, 19, 3, 56, 91, 20, 5, 79};
   int x = 55;
   cout << "In the array : ";
   for (int i = 0; i < 10; i++){
      cout << arr[i] << " ";
   }
   cout << "\nElement " << x;
   if (frontBack(arr, x)){
      cout << " is present.";
   }
   else{
      cout << " is not present.";
   }
   return 0;
}

Ausgabe

In the array : 21 43 10 19 3 56 91 20 5 79 
Element 55 is not present.

Zeitliche Komplexität – O(n/2), da die Suche von beiden Seiten die Zeit halbiert.

Raumkomplexität – O(1)

Beispiel

Im folgenden Programm nehmen wir den zweiten Fall eines String-Arrays. Rufen Sie die erste und die nächste Variable ab, während Sie das erste und das letzte Element überprüfen, um das erforderliche Element zu finden. Wenn das Element gefunden wird, geben Sie „true“ zurück, andernfalls gehen Sie zum nächsten Element und überprüfen Sie es erneut.

#include <bits/stdc++.h>
using namespace std;
// Function to front back search an element in the array
bool frontBack(string arr[], string x){
   int first = 0, last = 9;
   
   // loop execute till the element is found or traversal completes
   while (first <= last)    {
      if (arr[first] == x || arr[last] == x)        {
         return true;
      }
      first++; // Incrementing first
      last--; // Decrementing last
   }
   return false;
}
int main(){
   string arr[4] = {"hi", "high", "goat", "goa"};
   string x = "goat";
   cout << "In the array : ";
   for (int i = 0; i < 4; i++) {
      cout << arr[i] << ", ";
   }
   cout << "\nElement " << x;
   if (frontBack(arr, x)) {
      cout << " is present.";
   }
   else {
      cout << " is not present.";
   }
   return 0;
}

Ausgabe

In the array : hi, high, goat, goa, 
Element goat is present.

Zeitliche Komplexität – O(n/2), da die Suche von beiden Seiten die Zeit halbiert.

Raumkomplexität – O(1)

Fazit

Zusammenfassend lässt sich sagen, dass die Vorwärts- und Rückwärtssuche eines Arrays der üblichen linearen Suche ähnelt, mit der Ausnahme, dass zwei Elemente gleichzeitig überprüft werden, wodurch der Zeitaufwand halbiert wird. Dadurch wird die zeitliche Komplexität der Suche in einem unsortierten Array im ungünstigsten Fall von O(n) auf O(n/2) transformiert.

Das obige ist der detaillierte Inhalt vonSuche vorwärts und rückwärts im unsortierten Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!