2117

Można wykazać, że każdy algorytm wyszukujący metodą porównań w tablicy posortowanej ma pesymistyczną złożoność £l(log n). Zatem wyszukiwanie połówkowe jest optymalne w przypadku pesymistycznym.

Wyszukiwanie interpolacyjne

wersja "1 porównanie"

Metoda doskonała w przypadku średnim.

Intuicyjnie: jeśli szukany X ma wartość bliską wartości na końcu tablicy, to lepiej sprawdzać adres blisko tego końca.

Formalnie: stosujemy interpolację liniową - obliczamy nowe miejsce tak, aby różnica indeksów nowego miejsca i skrajnie lewego elementu była proporcjonalna do różnicy wartości elementu szukanego i skrajnie lewego elementu.

zamieniamy wiersz

M (L + R) DIV 2

przez ciąg instrukcji

M = L + r(X-a[L])*(r-l) / (a[R] - a[L])l if M = R then M--else if M = L then M++

a dodatkowo zakładamy, że n>2 oraz

a[l] <= x < a[n] (np. za pomocą wartowników).

Złożoność (liczba porównań):

• pesymistyczna: n + 0(1)

. średnia, przy założeniu że elementy słownika S wybrane z równomiernym rozkładem