Programme C++ pour rechercher des éléments dans un tableau trié et pivoté

Nous obtenons un tableau trié tournant autour d'un point. Nous obtenons également une clé pour rechercher dans le tableau. La logique utilisée pour rechercher des éléments dans ce tableau pivoté est -

• Tout d’abord, nous trouvons l’élément central du tableau. Si la clé existe, nous renvoyons que la clé existe dans le tableau.

• Si la clé n'est pas au milieu, on peut voir si la partie gauche du tableau (de gauche au centre) est triée. Si c'est trié, vous pouvez chercher la clé à gauche, sinon vous pouvez chercher la clé à droite (milieu+1, droite)

• Si la clé n'est pas trouvée au milieu et que la partie gauche n'est pas triée, alors nous trierons la partie droite, et nous pourrons alors voir si la clé existe dans la partie droite, ou nous rechercherons le côté gauche de le tableau dans la partie droite

• Sinon nous revenons introuvable.

Examinons quelques scénarios d'entrée et de sortie ci-dessous -

Imaginez qu'il existe un tableau composé de ses éléments. Par exemple, 2, 5, 7, 9, 11, après rotation, deviennent 5, 9, 11, 2, 7. Supposons que la clé du tableau soit 2.

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

Supposons un autre scénario dans lequel la clé ne se trouve pas dans le tableau spécifié.

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

Algorithme

Les étapes suivantes expliquent comment y parvenir.

• Trouvez l'élément central d'un tableau.

• Divisez le tableau en deux parties. (centre = gauche + droite) / 2

• Vérifiez si la clé est un élément intermédiaire.

• Sinon, vérifie l'élément sur le côté gauche du tableau et il est trié

• sinon si, cochez le bon élément (milieu+1, droite)

• Sinon si, triez la partie gauche et vérifiez

• Sinon, renvoyez l'élément introuvable.

Exemple

Par exemple, supposons que nous ayons un tableau "2,3,4,5,6,7,8" et que le tableau pivoté soit "5,6,7,8,2,3,4". La clé de ce tableau est 2.

L'implémentation C++ de cette opération est la suivante -

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

Sortie

2 is present

Conclusion

Une autre façon de résoudre ce problème est de trouver le point pivot ou l'index de rotation du tableau, puis d'effectuer une recherche binaire sur les bords. Notre méthode ne nécessite qu'une seule recherche binaire pour résoudre le problème. Chaque fois que nous voyons des tableaux de recherche et de tri, nous devons considérer la recherche binaire comme l'une des méthodes de recherche.

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!