Rechercher en avant et en arrière dans un tableau non trié

Tableau non trié - Un tableau est une structure de données constituée d'une collection d'éléments du même type. Un tableau non trié est une structure dans laquelle l'ordre des éléments est aléatoire, c'est-à-dire qu'à l'insertion, l'élément est ajouté au dernier élément quel que soit l'ordre des éléments précédents et la recherche dans un tel tableau ne souffre d'aucune aide des algorithmes de recherche en raison de manque de modèle pour le positionnement des éléments.

Recherche - Rechercher dans un tableau signifie rechercher un élément spécifique dans le tableau, qui peut renvoyer la position de l'élément souhaité ou une instruction booléenne spécifiant si l'élément est présent ou non dans le tableau.

• Recherche en avant - Rechercher en avant dans un tableau signifie effectuer une recherche linéaire dans le tableau à partir du 0ème index (c'est-à-dire le premier élément).

• Recherche inversée - Rechercher un tableau à l'envers signifie effectuer une recherche linéaire du tableau à partir du (n-1)ème index (c'est-à-dire le dernier élément).

Énoncé du problème

Étant donné un élément de recherche x, trouvez si x existe dans le cas suivant -

• Tableaux avec des éléments de même taille, tableaux d'entiers.

• Tableaux avec des éléments de différentes tailles, tableaux de chaînes.

Exemple 1

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

Output: TRUE

Explication - Dans le tableau donné, 4 apparaît au deuxième index.

Exemple 2

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

Output: False

Explication - Dans le tableau donné, "high" n'existe pas.

Solution

Comme mentionné ci-dessus, la recherche avant commence à partir du premier élément et la recherche arrière commence à partir du dernier élément. En combinant ces deux méthodes, le temps de recherche d'un élément dans le tableau peut être réduit de moitié puisque la première et la seconde moitié du tableau sont vérifiées simultanément.

Pour savoir si un élément apparaît dans un tableau, définissez premier et dernier comme premier et dernier éléments du tableau. Renvoie vrai si le premier ou le dernier élément est l'élément requis, sinon incrémente le premier élément de 1, décrémente le dernier élément de 1 et continue jusqu'à ce que l'élément soit trouvé. Si premier et dernier sont égaux lorsque le parcours est terminé, alors false est renvoyé si l'élément n'est pas trouvé.

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

Exemple : implémentation C++

Dans le programme suivant, nous prenons le premier cas de tableau entier. Obtenez les première et suivante variables tout en vérifiant le premier et le dernier élément pour trouver l'élément requis. Si l'élément est trouvé, retournez true, sinon passez à l'élément suivant et vérifiez à nouveau.

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

Sortie

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

Complexité temporelle - O(n/2) puisque la recherche des deux côtés réduit le temps de moitié.

Complexité spatiale - O(1)

Exemple

Dans le programme ci-dessous, nous prenons le deuxième cas de tableau de chaînes. Obtenez les première et suivante variables tout en vérifiant le premier et le dernier élément pour trouver l'élément requis. Si l'élément est trouvé, retournez true, sinon passez à l'élément suivant et vérifiez à nouveau.

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

Sortie

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

Complexité temporelle - O(n/2) puisque la recherche des deux côtés réduit le temps de moitié.

Complexité spatiale - O(1)

Conclusion

Pour résumer, la recherche avant et arrière d'un tableau est similaire à la recherche linéaire habituelle, sauf qu'elle vérifie deux éléments en même temps, réduisant ainsi la consommation de temps de moitié. Cela transforme la complexité temporelle dans le pire des cas de recherche dans un tableau non trié de O(n) à O(n/2).

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!