Algorytm działa na uporządkowanym zbiorze, który może być zapisany w tablicy statycznej, dynamicznej lub liście. Jest szybszy w działaniu niż przeszukiwanie binarne. W czystej postaci sprawdza się na zbiorze, w którym wzrost kolejnych elementów jest jednostajny (1,2,3,4,5…)Ale wprowadzając dodatkowe zabezpieczenie przed możliwością dzielenia przez ZERO może być zastosowany do dowolnego uporządkowanego zbioru (1,6,7,7,7,10,20,200,…) lub (1,100,156,980,1456,…) Kompletny opis- teoretyczny patrz książka „Algorytmy i struktury danych” autor Rod Stephens, wydawnictwo Helion.
Nasz zbiór będziemy przechowywać w tablicy dynamicznej zdefiniowanej na naszym własnym typie tTab (oczywiście lepszym rozwiązaniem byłby typ wskaźnikowy, którego wskaźniki byłby przechowywane w TList co nie jest trudne do zaimplementowania)
|
1 2 3 4 5 6 |
typ tTab=array of LongWord; var tablica:tTab;//tu ładujemy posortowane dane |
Nagłówek funkcji wyszukiwania
|
1 2 3 4 5 |
function PrzeszukiwanieInterpolacyjne(A:tTab;wartosc:longInt; L,P:LongInt; var kroki:LongInt):LongInt; |
gdzie:
A– zbiór wartości zapisanych w tablicy
Wartosc– to co szukamy
L,P– dolny i górny zakres zbioru (na przykład L:=0, P:=high(A) );
Kroki– informacja po ilu krokach znaleziono szukaną wartość (można z tego zrezygnować, zmienna wprowadzona jest teoretycznie aby można było porównać algorytm z przeszukiwaniem binarnym)
Ciało funkcji
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
function PrzeszukiwanieInterpolacyjne(a:tTab;wartosc:longInt; L,P:LongInt; var kroki:LongInt):LongInt; var srodek:LongInt; begin // -1 to sygnal braku szukanego elementu kroki:=0; while L<=P do begin //unikniecie dzielenia przez Zero if a[L]=a[P] then begin if a[L]=wartosc then result:=L else result:=-1; exit; end;//koniec a[L]=a[P] //znajdź nowe przyblizenie interpolacyjne srodek:=Round(L+(wartosc-a[L])*(P-L)/(a[P]-a[L])); //sprawdz czy wyliczony srodek miesci sie w zakresie tablicy if ((srodek<l)or(srodek>P))then begin Result:=-1; exit;//nie to wyskocz end;//Koniec testu granicy inc(kroki); //test znalezienia if wartosc=a[srodek]then begin //gdy znalazł result:=srodek; exit; end else //jak nie znalazł to obetnij zbior if wartosc<a[srodek] then="" <br=""> P:=srodek-1//szukaj w dolnej polowce zbioru else L:=srodek+1;//szukaj w gornej polowce zbioru //koniec obcinania end;//Koniec while L<=P result:=-1;//przymij ze nie znaleziono end;</a[srodek]></l)or(srodek> |
I to tyle
Pozdrawiam oksal Zbylitowska Góra 25.02.2007