Wyszukiwanie binarne

Zadanie 6 z 7 · rozdział 21Trudność: 2 z 3searchingbinary-searchlist

Treść zadania

Napisz funkcję wyszukiwanie_binarne(lista, klucz), która w liście posortowanej rosnąco znajduje indeks elementu równego klucz algorytmem wyszukiwania binarnego:

  1. Ustaw granice przeszukiwanego fragmentu: lo = 0, hi = n - 1.
  2. Dopóki lo <= hi:
    • wyznacz środek mid = (lo + hi) // 2 i zapamiętaj go na liście sprawdzonych indeksów,
    • jeśli lista[mid] == klucz — klucz znaleziony, wynikiem jest mid,
    • jeśli lista[mid] < klucz — klucz może być tylko na prawo od środka: lo = mid + 1,
    • w przeciwnym razie — tylko na lewo od środka: hi = mid - 1.
  3. Jeśli fragment stał się pusty (lo > hi), klucza nie ma w liście — wynikiem jest -1.

Funkcja wypisuje listę sprawdzonych indeksów i zwraca wynik, który program wypisuje w następnej linii.

Dane wejściowe

  • 1. linia: liczba elementów $n$
  • 2. linia: $n$ różnych liczb całkowitych posortowanych rosnąco, oddzielonych spacjami
  • 3. linia: liczba całkowita $x$ — szukany klucz

Dane wyjściowe

  • 1. linia: kolejno sprawdzane indeksy mid w formacie listy Pythona, np. [3, 5]
  • 2. linia: indeks elementu równego $x$ albo -1, jeśli takiego elementu nie ma

Ograniczenia

  • $1 \le n \le 1000$
  • Elementy listy są różne i są liczbami całkowitymi z przedziału $[-10^6, 10^6]$.

Uwagi

Uwagi o algorytmie:

  • Każde sprawdzenie zmniejsza przeszukiwany fragment mniej więcej o połowę, dlatego liczba sprawdzeń nie przekracza $\lfloor \log_2 n \rfloor + 1$ — dla $n = 1000$ to najwyżej 10 sprawdzeń, a dla miliona elementów najwyżej 20. Złożoność czasowa: $O(\log n)$.
  • Wyszukiwanie binarne działa tylko na liście posortowanej.

Przykład

Wejście
8
1 3 5 7 9 11 13 15
11
Wyjście
[3, 5]
5

Najpierw sprawdzamy mid = (0 + 7) // 2 = 3: lista[3] = 7 < 11, więc lo = 4. Potem mid = (4 + 7) // 2 = 5: lista[5] = 11 — znaleziono.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 21

Zadania w tym rozdziale polegają na samodzielnym zaimplementowaniu klasycznych algorytmów sortowania i wyszukiwania. Żeby było widać, że program naprawdę wykonuje dany algorytm, w każdym zadaniu wypisujesz stany pośrednie — listę po kolejnych krokach algorytmu albo kolejno sprawdzane pozycje.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Wejście ma zawsze tę samą postać: w 1. linii liczba elementów $n$, w 2. linii $n$ liczb całkowitych oddzielonych spacjami. Jeśli algorytm potrzebuje dodatkowej wartości (np. szukanego klucza), znajduje się ona w 3. linii.
  • Listę wypisuj w formacie Pythona — dokładnie tak, jak robi to print(lista), np. [1, 2, 4, 6, 27].
  • Sortujemy zawsze rosnąco (niemalejąco — liczby mogą się powtarzać).
  • Zaimplementuj algorytm samodzielnie. Nie używaj sorted(), list.sort(), list.index(), operatora in na liście ani innych gotowych funkcji sortujących i wyszukujących.
  • 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
1
5
5
Oczekiwane wyjście
[0]
0

Test 2

Nie uruchomiono
Wejście
1
5
7
Oczekiwane wyjście
[0]
-1

Test 3

Nie uruchomiono
Wejście
7
-10 -4 0 3 8 12 20
-10
Oczekiwane wyjście
[3, 1, 0]
0

Test 4

Nie uruchomiono
Wejście
7
-10 -4 0 3 8 12 20
21
Oczekiwane wyjście
[3, 5, 6]
-1

Test 5

Nie uruchomiono
Wejście
10
2 4 6 8 10 12 14 16 18 20
9
Oczekiwane wyjście
[4, 1, 2, 3]
-1

Test 6

Nie uruchomiono
Wejście
6
1 4 9 16 25 36
36
Oczekiwane wyjście
[2, 4, 5]
5
Uruchom z własnymi danymi