Porównania
Długość skoku
Wyszukiwanie liniowe potrzebowałoby

  • Szukana wartość
  • Bieżący blok
  • Porównywane
  • Wykluczone
  • Znalezione

Więcej o wyszukiwaniu skokowym

Wyszukiwanie skokowe

Wyszukiwanie skokowe leży między wyszukiwaniem liniowym a binarnym. Przechodzi przez posortowaną listę skokami o m miejsc i sprawdza tylko ostatnią wartość każdego bloku, aż dojdzie do bloku, którego ostatnia wartość nie jest mniejsza od szukanej. Wtedy przeszukuje ten blok od początku. Wybierz wartość i długość skoku i zobacz, ile porównań zajmują skoki i przeszukiwanie. Naciśnij Odtwórz, aby obejrzeć wyszukiwanie, albo Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Przerywana linia oznacza szukaną wartość, a zacieniona część to bieżący blok. Wyszukiwanie skokowe wymaga posortowanej listy, więc nieposortowana lista jest najpierw sortowana. Wybierz wartość, długość skoku, liczbę słupków albo wpisz własne liczby. Gdy plansza jest zaznaczona, strzałki przechodzą o krok, spacja uruchamia i wstrzymuje, a Home i End przenoszą na początek i na koniec.

Jak to działa

  1. Wybierz wartość do wyszukania, długość skoku i liczbę słupków. Albo wpisz własne liczby: wyszukiwanie skokowe najpierw je posortuje.
  2. Naciśnij Odtwórz albo użyj Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce wyszukiwania.
  3. Wypróbuj długość skoku 2 i 8 przy 40 słupkach i porównaj liczbę porównań z √n.

Jak działa wyszukiwanie skokowe

Podziel posortowaną listę na bloki po m wartości. Spójrz na ostatnią wartość pierwszego bloku. Jeśli jest mniejsza od szukanej, szukanej wartości nie może być nigdzie w tym bloku, więc skocz na koniec następnego bloku i sprawdź znowu. Gdy tylko ostatnia wartość bloku nie jest mniejsza, szukana wartość może być tylko w tym bloku: wróć do jego początku i sprawdzaj wartości po kolei, aż znajdziesz szukaną albo ją miniesz.

Wybór długości skoku

Przy n wartościach skoki zajmują do n/m porównań, a przeszukiwanie do m. Krótkie skoki skracają przeszukiwanie, ale skoków jest wiele; długie skoki działają odwrotnie. Suma n/m + m jest najmniejsza dla m = √n, co daje około 2√n porównań: najwyżej 13 dla 40 wartości, wobec 40 w wyszukiwaniu liniowym i 6 w binarnym. Wyszukiwanie skokowe nigdy nie cofa się o więcej niż jeden blok, co pomaga, gdy cofanie się w danych jest wolne.

Często zadawane pytania

Jak działa wyszukiwanie skokowe?

Na posortowanej liście skacze do przodu co m miejsc i sprawdza ostatnią wartość każdego bloku. Gdy ta wartość nie jest już mniejsza od szukanej, szukana wartość może być tylko w tym bloku, który wtedy przeszukuje od początku.

Jaka długość skoku jest najlepsza?

√n, zaokrąglone. Skoki kosztują do n/m porównań, a przeszukiwanie do m, i ich suma jest najmniejsza, gdy obie części są równe, czyli dla m = √n. Daje to w najgorszym przypadku około 2√n porównań.

Czy wyszukiwanie skokowe jest szybsze od binarnego?

Nie, wyszukiwanie binarne potrzebuje mniej porównań: około log₂ n wobec około 2√n. Wyszukiwanie skokowe może jednak wygrać, gdy cofanie się w danych jest kosztowne, bo cofa się tylko raz, na początek jednego bloku.

Które wystąpienie znajduje, gdy wartości się powtarzają?

Pierwsze. Każdy pominięty blok kończy się wartością mniejszą od szukanej, więc żaden wcześniejszy blok nie może jej zawierać, a przeszukiwanie zaczyna się od początku bloku.

Czy moje liczby są gdzieś wysyłane?

Nie. Wyszukiwanie działa w twojej przeglądarce, a ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora