Algorytm, który omówimy w tym punkcie jest tylko nieznaczną modyfikacją omawianej poprzednio metody sekwencyjnego poszukiwania w ciągu uporządkowanym.

Zastanówmy się, jak wyglądają nasze poszukiwania w książce telefonicznej. Oczywiście zakładamy, że wszystkie zawarte w niej informacje są uporządkowane ze względu na porządek alfabetyczny. Jeśli zupełnie nie wiemy, w której części książki znajduje się szukana przez nas pozycja, a książka jest gruba, to zwykle zniechęcamy się przewracaniem kolejno kartki po kartce i przyspieszamy proces poszukiwania przerzucając po kilka, lub kilkanaście kartek na raz i sprawdzając za każdym razem, czy już minęliśmy szukane hasło, czy też jeszcze trzeba szukać dalej. Jeśli już przeskoczyliśmy kartkę z szukanym hasłem, to postępujemy teraz ostrożniej np. cofając się kartka po kartce aż do znalezienia szukanej pozycji. Czy nie tak wyglądają Państwa poszukiwania w książce telefonicznej, czy w słowniku?

Spróbujmy teraz sformalizować opisaną wyżej metodę. Zakładamy, tak jak poprzednio, że elementy przeszukiwanego zbioru są umieszczone w tablicy na pozycjach e[1],...,e[n] w porządku rosnących wartości. Dodatkowo przyjmiemy, że poszukiwany element x mieści się w przedziale wyznaczonym przez pierwszy i ostatni element ciągu. Zadanie niech polega na ustaleniu najmniejszego przedziału utworzonego przez elementy ciągu, w którym mieści się x. Specyfikacja szukanego algorytmu będzie tym razem następująca:

wp = {n>0, e[1] < e[2] <... < e[n],  e[1] £ x < e[n]},   wk =  {e[result] £ x £ e[result+1],  1 £ result £ n}.

Metoda:  Porównujemy element x z co czwartym elementem danego ciągu tak długo aż znajdziemy element większy od x. Wtedy przeszukujemy sekwencyjnie (co najwyżej) cztery elementy poprzedzające.  

W przedstawionym poniżej algorytmie użyliśmy  instrukcji exit, która umożliwia natychmiastowe opuszczenie pętli i przejście do wykonywania następujących po niej instrukcji.                  

Poprawność: Zauważmy najpierw, że jeśli rozważany ciąg ma mniej niż 5 elementów, to nie wejdziemy do pierwszej pętli. Druga zaś jest znanym nam przeszukiwaniem sekwencyjnym, z tym, że cofamy się zaczynając od przedostatniego elementu ciągu (elementu ostatniego nie warto sprawdzać, bo z założenia  x< e[n]).

Spróbujmy teraz przeanalizować działanie algorytmu w celu ustalenia niezmiennika pierwszej pętli. Załóżmy, że jesteśmy wewnątrz pętli, tuż po sprawdzeniu testu (i < n ), oraz  e[j] £ x  dla 0< j  £ i-4, tzn. x nie jest mniejsze od wszystkich elementów ciągu o numerach co najmniej o 4 mniejszych od aktualnej wartości i. Po sprawdzeniu warunku (x < e[i]) albo wyjdziemy z pętli, wiedząc, że x mieści się między e[i-4] a e[i], albo stwierdzimy, że x nie jest mniejsze od wszystkich elementów ciągu aż do pozycji i. Teraz jednak, zgodnie z treścią pętli, zwiększymy wartość zmiennej i  o 4. W konsekwencji znów wiemy, że x nie jest mniejsze od wszystkich elementów ciągu o numerach co najmniej o 4 mniejszych od obecnej wartości i, e[j] £ x  dla 0< j  £ i-4. Ponadto, jeżeli wchodzimy do pętli z wartością i spełniającą  i-4 < n, to warunek pętli gwarantuje, że również i<n. Zatem, nawet jeśli zwiększymy w tej iteracji wartość i o 4, znów spełniona będzie własność  i-4 < n.

Niezmiennikiem pierwszej pętli jest więc formuła    i-4 < n oraz   e[j] £ x  dla 0< j  £ i-4.

Jeżeli opuszczamy pętlę  wykonując instrukcję exit, to oczywiście zależności, które były w tym momencie prawdziwe (np. niezmiennik), nadal zachodzą. Wiemy jednak dodatkowo, że x<e[i]. Jeżeli opuszczamy pętlę, ponieważ i>n, to znów niezmiennik jest spełniony. Ostatecznie do wyjściu z pierwszej pętli prawdziwa jest formuła

(e[i-4] £ x Ù (i-4)<n Ù x<e[i] Ù i< n)  Ú (n £ i Ù e[i-4] £ x Ù (i-4)<n Ù x<e[n])

W drugim członie tej alternatywy dopisaliśmy zależność x<e[n], która wynika z przyjętego warunku początkowego.

Pozostało jeszcze sprawdzić co dzieje się w drugiej pętli. Przed wejściem do drugiej pętli x<e[k+1]. Jeżeli po "do" spełniony jest warunek x<e[k+1], to ponieważ musieliśmy przejść przez test, wiemy dodatkowo, że x<e[k] oraz k> i-4. Zatem po wykonaniu instrukcji k := k-1, znów x<e[k+1]. Ponadto cały czas prawdziwa jest formuła i-4  £ k. Jeżeli i=4, to w drugiej pętli, k możemy zmniejszyć tylko do 1, bo na mocy warunku początkowego e[1]£ x. Wynika stąd, że niezmiennikiem drugiej pętli jest formuła ( x<e[k+1] Ù  i-4 < k). Wyjście z drugiej pętli nastąpi albo, gdy k= i-4, albo,  gdy e[k] £ x. Zatem po wyjściu z drugiej pętli mamy

albo k= i-4 Ù  x < e[k+1]  albo i-4 < k  Ù  e[k] £ x  Ù  x < e[k+1].

Biorąc pod uwagę, że przy wejściu do drugiej pętli spełniony był warunek e[i-4] £ x dla i >4 lub  e[1]£ x  dla i=4, otrzymujemy ostatecznie  e[k] £ x < e[k+1], i ta właśnie wartość k jest przypisana zmiennej result.

Pytanie 3: Ile porównań wykona algorytm wyszukiwania Skoki, jeżeli ciąg składa się ze stu elementów oraz wiadomo, że szukany element spełnia warunek e[1] £ x <e[2]?

Koszt algorytmu: W najgorszym razie przejdziemy krokami "co 4" cały ciąg nie znajdując odpowiedzi (nie porównujemy x z elementem  ostatnim nawet, gdy n jest podzielne przez 4, bo warunkiem pętli jest i<n). Musimy się wtedy cofnąć i przejrzeć osobno pominięte  3 elementy. Pesymistyczny algorytmu, mierzony liczbą wykonanych porównań, wynosi : W(n)= [(n-1)/4]+3.

Na koniec, zauważmy, że nic nie stoi na przeszkodzie, aby wykonywać większe "skoki". Pozostawiamy Czytelnikowi zadanie, przekształcenia algorytmu skoki do postaci procedury  SKOKI(k), której parametr k określałby długość wykonywanego "skoku". Oczywista modyfikacja polegać będzie na zamianie liczby 4 na k. Jasne jest też, że tak zmodyfikowany algorytm wykona w najgorszym razie [(n-1)/k] + k-1 porównań.

Pytanie 4: Dla jakich wartości k algorytm  SKOKI(k) ma najmniejszy koszt pesymistyczny?

Zobacz odpowiedź