Indeks klucza w cyklicznie posortowanej liście

Zadanie 7 z 9 · rozdział 22Trudność: 2 z 3binary searchrotacjalist

Treść zadania

Lista liczb całkowitych była posortowana rosnąco, a następnie została cyklicznie przesunięta (jej początkowy fragment przeniesiono na koniec), np. 1 2 3 4 5 6 → 3 4 5 6 1 2. Znajdź indeks (liczony od 0), pod którym w tej liście znajduje się podany klucz. Jeśli klucza nie ma w liście, wypisz -1.

Dane wejściowe

  • 1. linia: liczba elementów $N$
  • 2. linia: $N$ liczb całkowitych oddzielonych spacjami — cyklicznie przesunięta lista rosnąca
  • 3. linia: liczba całkowita $x$ — szukany klucz

Dane wyjściowe

  • 1. linia: indeks elementu równego $x$ albo -1

Ograniczenia

  • $1 \le N \le 1000$
  • Wszystkie elementy listy są różne.
  • Przesunięcie może wynosić 0 (lista jest wtedy po prostu posortowana).

Uwagi

  • Zadanie da się rozwiązać w czasie $O(\log N)$ zmodyfikowanym wyszukiwaniem binarnym: po podziale przedziału na pół co najmniej jedna z połówek jest posortowana rosnąco — sprawdź, czy klucz mieści się w jej zakresie, i na tej podstawie wybierz połowę do dalszego przeszukiwania.
  • To rozwinięcie zwykłego wyszukiwania binarnego — zob. zadanie „Wyszukiwanie binarne” z rozdziału 21.

Przykład

Wejście
6
3 4 5 6 1 2
4
Wyjście
1

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 22

Zadania w tym rozdziale pokazują, jak sortować w praktyce: napisy, słowa, pary, obiekty — często według własnego kryterium. Tutaj wolno (a nawet warto) korzystać z wbudowanych narzędzi Pythona: sorted(), list.sort() i parametru key=.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Jeśli wejściem jest napis — wczytaj całą linię (łącznie ze spacjami).
  • Jeśli wejściem jest lista — najpierw podana jest liczba elementów $N$, a potem elementy (w jednej linii albo w kolejnych liniach — zależnie od zadania).
  • Napisy porównujemy tak jak Python, czyli według kodów znaków Unicode: wielkie litery są „mniejsze” od małych ('Z' < 'a'), a polskie litery są „większe” od wszystkich liter alfabetu łacińskiego ('z' < 'ą').
  • Sortowanie w Pythonie (sorted(), list.sort()) jest stabilne: elementy równe według kryterium sortowania zachowują kolejność z wejścia. Korzystają z tego zadania, w których mogą wystąpić remisy.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
5
4 5 6 1 2
3
Oczekiwane wyjście
-1

Test 2

Nie uruchomiono
Wejście
1
7
7
Oczekiwane wyjście
0

Test 3

Nie uruchomiono
Wejście
1
7
3
Oczekiwane wyjście
-1

Test 4

Nie uruchomiono
Wejście
8
27 31 32 3 5 9 10 15
31
Oczekiwane wyjście
1

Test 5

Nie uruchomiono
Wejście
9
4 7 12 32 51 90 100 1 2
-5
Oczekiwane wyjście
-1

Test 6

Nie uruchomiono
Wejście
6
1 2 3 4 5 6
6
Oczekiwane wyjście
5

Test 7

Nie uruchomiono
Wejście
7
10 20 30 40 50 -5 0
-5
Oczekiwane wyjście
5

Test 8

Nie uruchomiono
Wejście
4
9 1 3 5
9
Oczekiwane wyjście
0

Test 9

Nie uruchomiono
Wejście
6
3 4 5 6 1 2
2
Oczekiwane wyjście
5
Uruchom z własnymi danymi