Gymnastique algorithmique 3

Search Rotated Array Un tableau trié qui a été tourné vers la droite d'un nombre arbitraire et le nombre spécifié (clé) sont transmis et recherchés.

La description

Recherche le nombre spécifié (clé) dans un tableau trié qui a subi une rotation de n'importe quel nombre. Renvoie -1 si la clé n'existe pas. Supposons que le tableau ne contienne aucun doublon. Vous trouverez ci-dessous le tableau d'origine avant la rotation. Si vous exécutez la rotation 6 fois sur ce tableau, elle changera comme suit.

conditions

1. La recherche linéaire O (n) est une solution inacceptable.
2. Considérez la recherche binaire modifiée.

Solution Runtime Complexity O(logn) J'utilise la recherche binaire. Memory Complexity O(logn). Pour chaque boucle, le tableau passé est coupé en deux et un seul est recherché.

Commentaire

La solution est essentiellement la recherche binaire, mais avec quelques corrections. Si vous regardez attentivement l'exemple de tableau, vous pouvez voir qu'au moins la moitié du tableau est toujours triée. Profitez de cette fonctionnalité. Si le nombre n que vous recherchez se trouve dans la moitié triée du tableau, vous pouvez le trouver avec la recherche binaire. Sinon, jetez les moitiés triées et continuez à examiner les moitiés non triées. Cela entraîne une complexité d'exécution de O (logn) car chaque étape divise le tableau en deux. Certaines parties conditionnelles du code sont un peu difficiles à lire. Sous quatre conditions

1. Lorsque le SubArray dans la plage de début ~ mi coupé en deux est ** trié ** et que la clé que vous recherchez existe dans cette plage.
2. Lorsque le SubArray dans la plage du milieu à la fin coupé en deux est ** trié ** et que la clé que vous recherchez existe dans cette plage.
3. Lorsque le SubArray dans la plage de start ~ mid cut in half n'est pas ** trié ** et que la clé que vous recherchez existe dans cette plage.
4. Lorsque le SubArray dans la plage intermédiaire à la fin coupée en deux n'est pas ** trié ** et que la clé que vous recherchez existe dans cette plage. Les conditions sont divisées en tant que telles.

la mise en oeuvre

tester

Production