Cerință
Un șir strict crescător a fost rotit circular cu un număr necunoscut de poziții, posibil zero. Găsește poziția valorii x în șirul primit. Proiectează căutarea astfel încât să facă O(log n) comparații după citirea datelor.
Tip de problemă: Search in Rotated Sorted Array.
Date de intrare
Se citesc n și x, apoi n elemente distincte ale șirului rotit.
Date de ieșire
Afișează poziția de la 1 la n sau -1 dacă x nu apare.
Restricții
1 ≤ n ≤ 2000; -1000000000 ≤ x,a[i] ≤ 1000000000.
Observații
Raportată de un candidat: Search in Rotated Sorted Array la Amazon (SDE2, Bellevue, noiembrie 2019).
Adaptare Algo25: Elemente distincte și poziții de la 1; -1 când ținta lipsește.
Sursa relatării: https://leetcode.com/discuss/post/438583/amazon-sde2-bellevue-nov-2019-reject/
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. Valorile sunt distincte. O rotire circulară poate muta începutul șirului în interior; indicii rămân cei ai șirului primit.Mărește schema ↗Date de intrare
5 4
9 12 2 4 7
Date de ieșire
4
Exemplul 2
Date de intrare
1 3
8
Date de ieșire
-1
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →