[Jurk]

Wyszukiwanie interpolacyjne (Algorytmy i struktury danych – Rod Stephens)

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)

Kod:

typ tTab=array of LongWord; Kod: var tablica:tTab;//tu ładujemy posortowane dane

Nagłówek funkcji wyszukiwania

Kod:

function PrzeszukiwanieInterpolacyjne(A:tTab;wartosc:longInt;                                         L,P:LongInt;                                         var kroki:LongInt):LongInt;

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

Kod:

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       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;

I to tyle