[JAVA] 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. Screen Shot 2019-12-17 at 15.15.54.png Si vous exécutez la rotation 6 fois sur ce tableau, elle changera comme suit. Screen Shot 2019-12-17 at 15.18.04.png

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

Screen Shot 2019-12-17 at 16.05.32.png

tester

Screen Shot 2019-12-17 at 16.07.05.png

Production

Screen Shot 2019-12-17 at 16.09.54.png

Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Exercices d'algorithme 13
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes