1
Symulacja 1

Przeanalizuj symulację interaktywną, która wizualizuje metodę „dziel i zwyciężaj” na przykładzie wyszukiwania binarnego.

W symulacji możesz wprowadzić własną listę (pamiętaj, by była posortowana) oraz szukany element. Symulacja ilustruje, w jaki sposób z listy liczb wyodrębniane są coraz mniejsze listy, zgodnie z metodą „dziel i zwyciężaj”.

Symulacja obrazująca wyszukiwanie binarne

RwEMzpycaGxEC

Przeanalizuj metodę „dziel i zwyciężaj” na przykładzie przedstawionego wyszukiwania binarnego.

Ilustracja interaktywna przedstawia 2 pola tekstowe, do których można wpisać kolejno posortowaną listę oraz szukany element. Obok tych pól umieszczono 2 przyciski: następny krok oraz reset. Pod tym segmentem umieszczono zmieniający się tekst: liczba wykonanych kroków, po czym umieszczono liczbę kroków. Pod wszystkimi elementami znajduje się ilustracja przedstawiająca działanie algorytmu.

Algorytm zaczyna pracę od podzielenia listy na 2 przedziały, umieszcza wyszukujący blok po środku, po czym testuje, czy jest on większy od szukanej liczby. W zależności od wyniku tego porównania, algorytm wybierze lewą lub prawą stronę listy. Krok ten skraca listę dwukrotnie, zatem przy długości listy 1 wymagane jest sprawdzenie, czy liczba aktualnie sprawdzana jest równa, a nie większa od szukanej.

Na powyższej ilustracji znajduje się lista 1, 2, 5, 6, 8, 9, 12, 13, 14, 20 oraz 32

Szukaną liczbą jest 8.

Algorytm porównuje środkową liczbę z przedziału z szukaną. Jest to porównanie, czy 9 jest większe od 8.

Ponieważ 9 jest większe od 8, przeszukiwana lista skończy się na elemencie listy o jeden przed 9.

Wybrano nowy punkt środkowy, jest to 5; Wykonane porównanie to, czy 5 jest mniejsze od 8.

Ponieważ jest to prawda, ustalona nowa przeszukiwana lista skrócona została ponownie, zaczyna się ona od elementu o jeden po uprzednio sprawdzonej liczbie 5.

Kolejnym krokiem jest sprawdzenie, czy liczba sprawdzana, czyli 6, jest mniejsza od 8.

Ponieważ jest to prawda, lista zostaje ponownie skrócona, tym razem jest ona listą jednoelementową.

Sprawdzamy prawdziwość ostatniego porównania, czy szukana liczba jest równa liczbie wybranej z listy, czyli czy 8 jest równe 8.

Ponieważ jest to prawda, algorytm odnalazł szukaną liczbę.

1
Polecenie 1

Zaproponuj własne dane do wprowadzenia do symulacji. Podaj liczbę kroków dla tych danych.

Polecenie 2
RAgkzarPsE3PT
Polecenie 3
RV4rTpjqZLwQB
xxxxx
Polecenie 4
RVS6ODX4jpWbf
xx