W tym punkcie rozważymy problem wyszukiwania przy założeniu, że przeszukiwany ciąg jest podzbiorem pewnego liniowo uporządkowanego zbioru i sam jest uporządkowany.

Problem: Dany jest element x oraz ciąg n elementowy uporządkowany rosnąco. Zadanie polega na znalezieniu takiego przedziału, wyznaczonego przez kolejne elementy ciągu, do którego x należy, lub stwierdzenie, że x do tego ciągu nie należy.

Załóżmy tak jak poprzednio, że elementy ciągu są zapisane w tablicy e na pozycjach e[1], e[2], ..., e[n] i niech specyfikacja poszukiwanego algorytmu będzie następująca:

wk = {(x < e[1] Ù result = 0) Ú ( e[n] £ x Ù result = n) Ú (result = i Ù i < n Ù e[i] £ x < e[i+1])}.

Przyjęliśmy więc, że wynikiem algorytmu ma być liczba 0, gdy x jest liczbą mniejszą od wszystkich elementów ciągu (x<e[1]), liczba n, gdy x jest niemniejsze od wszystkich elementów ciągu, lub liczba i, 1 £ i £ n, gdy e[i] £ x < e[i+1].

Metoda: Pierwsze najprostsze rozwiązanie, to sekwencyjne przeszukanie ciągu. Najpierw rozważymy przypadek, gdy szukany element x nie mieści się w żadnym przedziale wyznaczonym przez elementy danego ciągu. Jeśli obie sytuacje x < e[1] i e[n] £ x są już wykluczone, to wiemy na pewno, że e[i] £ x < e[n]. Aby ustalić właściwą odpowiedź, wystarczy teraz porównywać x z kolejnymi elementami ciągu.

ALGORYTM

Search	{

	if x< e[1] then i := 0 else	// i=0, gdy x jest mniejsze od wszystkich elementów ciągu
	if e[n] £ x then i := n else	// i=n, gdy x jest równy lub większy od e[n]
	i := 1;	// e[1] £ x < e[n]
	while (not x < e[i+1]) do	// e[i] £ x oraz e[i+1] £ x
	i := i+1	// e[i] £ x
	od ;	// e[i] £ x oraz x < e[i+1]
	fi fi ;
	result := i;
}

Niezmiennikiem pętli w tym algorytmie jest formuła e[i] £ x. Rzeczywiście, jeżeli spełniony jest warunek pętli (not x < e[i+1]) oraz e[i] £ x dla pewnej wartości i, to wiemy również, że e[i+1] £ x. Po wykonaniu jedynej instrukcji pętli i := i+1, x spełnia zależność e[i]£ x. Ponieważ formuła e[i] £ x jest spełniona przed pierwszym wejściem do pętli (i jest wtedy równe 1), oraz jest jej niezmiennikiem, zatem na mocy twierdzenia o niezmienniku (por. wykład 1.4), po wyjściu z pętli też będzie spełniona. Skoro wyszliśmy z pętli, to stało się tak dlatego, że warunek (not x < e[i+1]) nie był spełniony. Mamy więc e[i] £ x oraz x < e[i+1], a zmienna result przyjmie właśnie wartość i.

Zastanówmy się jeszcze nad problemem zatrzymywania się tego algorytmu. Jeżeli nie zachodzi żaden z dwóch pierwszych warunków (x< e[1], e[n] £ x ), to wiemy na pewno, że e[1] £ x < e[n]. Wynika to z założenia, że relacja £ jest liniowym porządkiem, a ciąg jest rosnący. W konsekwencji zmienna i nie może przyjąć wartości większej od n. Pętla zatrzyma się po co najwyżej n-1 krokach dla wszystkich danych spełniających warunek początkowy. Możemy więc sformułować twierdzenie:

Twierdzenie 2.1

Algorytm Search jest całkowicie poprawny ze względu na warunek początkowy wp = {n > 0, e[1]< e[2]< ... < e[n]} i warunek końcowy wk = {(x < e[1] Ù result = 0) Ú ( e[n] £ x Ù result = n) Ú (result = i Ù i < n Ù e[i] £ x < e[i+1])} w dowolnej strukturze danych z porządkiem liniowym £.

Analiza kosztu omawianego tu algorytmu jest bardzo podobna do analizy przedstawionej w punkcie 1. Jako operację dominującą wybierzmy porównywanie elementów ciągu. W najgorszym razie algorytm wykona 2 + (n-1) porównań przeglądając wszystkie elementy ciągu, gdyż przypadek najgorszy dla naszego algorytmu, to e[n-1] £ x < e[n].

Aby oszacować koszt średni przyjmijmy pewne uproszczenia. Po pierwsze założymy, że strukturą danych dla naszego algorytmu jest zbiór liczb rzeczywistych oraz, że zarówno x jak i elementy ciągu mieszczą się w przedziale [a, b] wyznaczonym przez pewne liczby rzeczywiste a, b, a<b. Niech dla uproszczenia notacji e[0]=a oraz e[n+1]=b. W ten sposób obszar naszych poszukiwań składa się z n+1 przedziałów: e[0]-e[1], e[1]-e[2], itd. e[n-1]-e[n], e[n]-e[n+1]. Założymy ponadto, że prawdopodobieństwo tego, że x przyjmuje dowolną wartość c z przedziału [a, b] jest dla wszystkich c taka sama. Prawdopodobieństwo tego, że x znajduje się w jakimś ustalonym przedziale można zmierzyć stosunkiem długości rozważanego przedziału do długości całego obszaru:

Zauważmy, że niezależnie od tego jaka jest konkretna wartość zmiennej x, jeżeli x Î [e[0],e[1]], to algorytm Search wykona jedno porównanie, jeżeli x Î [e[n],e[n+1]], wykona 2 porównania, a gdy x Î [e[i],e[i+1]], gdzie 0<i<n, wykona (2 + i) porównań. Oczekiwaną liczbę porównań wykonaną przez algorytm Search policzymy ze wzoru:

A(Search,n) = P(x Î [e[0],e[1]]) ´ 1 + P(x Î [e[n],e[n+1]]) ´ 2 + S_0<i<n P(x Î [e[i],e[i+1]]) (2+i).

Oczywiście, tę ostatnią sumę można oszacować z góry przez 2+(n-1), co nie jest wynikiem specjalnie interesującym. Jeżeli natomiast dodatkowo założymy, że długości przedziałów [e[i+1],e[i]] wyznaczonych przez kolejne elementy ciągu są takie same, to P(x Î [e[i],e[i+1]]) = 1/(n+1).

Uwaga. Jeżeli wiemy, że szukany element znajduje się w przedziale wyznaczonym przez pierwszy i ostatni element ciągu, to w algorytmie Search możemy pominąć dwa pierwsze porównania.

Pytanie 2: Jaka jest oczekiwana liczba porównań wykonanych przez algorytm Search (zmodyfikowanym tak jak w powyżej Uwadze), jeśli został on zastosowany do ciągu 0,4,8,16,32, a rozważaną strukturą danych są liczby naturalne i wiemy, że szukany element x jest liczbą naturalną spełniającą warunek 0<x<33?