recherche
Maisondéveloppement back-endC++Programme C++ pour rechercher des éléments dans un tableau trié et pivoté

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!

Déclaration
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer
La communauté C: ressources, soutien et développementLa communauté C: ressources, soutien et développementApr 13, 2025 am 12:01 AM

C Les apprenants et les développeurs peuvent obtenir des ressources et le soutien de Stackoverflow, des cours R / CPP de Reddit, Coursera et EDX, des projets open source sur GitHub, des services de conseil professionnel et CPPCON. 1. StackOverflow fournit des réponses aux questions techniques; 2. La communauté R / CPP de Reddit partage les dernières nouvelles; 3. Coursera et Edx fournissent des cours de C officiels; 4. Projets open source sur GitHub tels que LLVM et Boost Améliorer les compétences; 5. Les services de conseil professionnel tels que Jetbrains et Perforce fournissent un support technique; 6. CPPCON et d'autres conférences aident les carrières

C # vs C: où chaque langue excelleC # vs C: où chaque langue excelleApr 12, 2025 am 12:08 AM

C # convient aux projets qui nécessitent une efficacité de développement élevée et un support multiplateforme, tandis que C convient aux applications qui nécessitent des performances élevées et un contrôle sous-jacent. 1) C # simplifie le développement, fournit une collection de déchets et des bibliothèques de classe riches, adaptées aux applications au niveau de l'entreprise. 2) C permet un fonctionnement de la mémoire directe, adapté au développement de jeux et à l'informatique haute performance.

L'utilisation continue de C: Raisons de son enduranceL'utilisation continue de C: Raisons de son enduranceApr 11, 2025 am 12:02 AM

C Les raisons de l'utilisation continue incluent ses caractéristiques élevées, une application large et en évolution. 1) Performances à haute efficacité: C fonctionne parfaitement dans la programmation système et le calcul haute performance en manipulant directement la mémoire et le matériel. 2) Largement utilisé: briller dans les domaines du développement de jeux, des systèmes intégrés, etc. 3) Évolution continue: depuis sa sortie en 1983, C a continué à ajouter de nouvelles fonctionnalités pour maintenir sa compétitivité.

L'avenir de C et XML: tendances et technologies émergentesL'avenir de C et XML: tendances et technologies émergentesApr 10, 2025 am 09:28 AM

Les tendances futures de développement de C et XML sont: 1) C introduira de nouvelles fonctionnalités telles que les modules, les concepts et les coroutines à travers les normes C 20 et C 23 pour améliorer l'efficacité et la sécurité de la programmation; 2) XML continuera d'occuper une position importante dans les fichiers d'échange de données et de configuration, mais sera confronté aux défis de JSON et YAML, et se développera dans une direction plus concise et facile à analyser, telles que les améliorations de XMLSChema1.1 et XPATH3.1.

Modèles de conception C modernes: construire un logiciel évolutif et maintenableModèles de conception C modernes: construire un logiciel évolutif et maintenableApr 09, 2025 am 12:06 AM

Le modèle de conception C moderne utilise de nouvelles fonctionnalités de C 11 et au-delà pour aider à créer des logiciels plus flexibles et efficaces. 1) Utilisez des expressions lambda et de la fonction std :: pour simplifier le modèle d'observateur. 2) Optimiser les performances grâce à la sémantique mobile et à un transfert parfait. 3) Les conseils intelligents garantissent la sécurité et la gestion des ressources.

C multithreading et concurrence: maîtriser la programmation parallèleC multithreading et concurrence: maîtriser la programmation parallèleApr 08, 2025 am 12:10 AM

C Les concepts de base de la lecture multithre et de la programmation simultanée incluent la création et la gestion de threads, la synchronisation et l'exclusion mutuelle, les variables conditionnelles, la mise en commun des threads, la programmation asynchrone, les erreurs courantes et les techniques de débogage, et l'optimisation des performances et les meilleures pratiques. 1) Créez des threads à l'aide de la classe de threads std ::. L'exemple montre comment créer et attendre que le fil se termine. 2) Synchroniser et exclusion mutuelle pour utiliser STD :: Mutex et STD :: Lock_guard pour protéger les ressources partagées et éviter la concurrence des données. 3) Les variables de condition réalisent la communication et la synchronisation entre les threads via STD :: Condition_variable. 4) L'exemple de pool de threads montre comment utiliser la classe Threadpool pour traiter les tâches en parallèle pour améliorer l'efficacité. 5) La programmation asynchrone utilise Std :: comme

C Dive profonde: maîtrise la gestion de la mémoire, les pointeurs et les modèlesC Dive profonde: maîtrise la gestion de la mémoire, les pointeurs et les modèlesApr 07, 2025 am 12:11 AM

La gestion de la mémoire de C, les pointeurs et les modèles sont des caractéristiques de base. 1. La gestion de la mémoire alloue et libère manuellement la mémoire par le biais de nouvelles et de suppression, et prêtez attention à la différence entre le tas et la pile. 2. Les pointeurs permettent un fonctionnement direct des adresses mémoire et les utilisent avec prudence. Les pointeurs intelligents peuvent simplifier la gestion. 3. Le modèle implémente la programmation générique, améliore la réutilisabilité et la flexibilité du code, et doit comprendre la dérivation et la spécialisation du type.

CHARRAMMAGE C ETCHARRAMMAGE C ETApr 06, 2025 am 12:06 AM

C convient à la programmation système et à l'interaction matérielle car elle fournit des capacités de contrôle proches du matériel et des fonctionnalités puissantes de la programmation orientée objet. 1) C Grâce à des fonctionnalités de bas niveau telles que le pointeur, la gestion de la mémoire et le fonctionnement des bits, un fonctionnement efficace au niveau du système peut être réalisé. 2) L'interaction matérielle est implémentée via des pilotes de périphérique, et C peut écrire ces pilotes pour gérer la communication avec des périphériques matériels.

See all articles

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
3 Il y a quelques semainesBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Meilleurs paramètres graphiques
3 Il y a quelques semainesBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Comment réparer l'audio si vous n'entendez personne
3 Il y a quelques semainesBy尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Comment déverrouiller tout dans Myrise
4 Il y a quelques semainesBy尊渡假赌尊渡假赌尊渡假赌

Outils chauds

MantisBT

MantisBT

Mantis est un outil Web de suivi des défauts facile à déployer, conçu pour faciliter le suivi des défauts des produits. Cela nécessite PHP, MySQL et un serveur Web. Découvrez nos services de démonstration et d'hébergement.

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

MinGW - GNU minimaliste pour Windows

MinGW - GNU minimaliste pour Windows

Ce projet est en cours de migration vers osdn.net/projects/mingw, vous pouvez continuer à nous suivre là-bas. MinGW : un port Windows natif de GNU Compiler Collection (GCC), des bibliothèques d'importation et des fichiers d'en-tête librement distribuables pour la création d'applications Windows natives ; inclut des extensions du runtime MSVC pour prendre en charge la fonctionnalité C99. Tous les logiciels MinGW peuvent fonctionner sur les plates-formes Windows 64 bits.

PhpStorm version Mac

PhpStorm version Mac

Le dernier (2018.2.1) outil de développement intégré PHP professionnel

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser