Algorytmy i Struktury Danych - Wyszukiwanie interpolacyjne

Opisane w poprzednim rozdziale wyszukiwanie binarne (ang. binary search) zawsze szuka elementu o kluczu k w środku zbioru. Tymczasem, jeśli założymy liniowy rozkład wartości elementów w przeszukiwanym zbiorze, to możemy precyzyjniej wytypować spodziewaną pozycję poszukiwanego klucza na podstawie jego wartości. Wzór jest następujący:

Z	– przeszukiwany zbiór.
k	– poszukiwana wartość.
i_p	– indeks pierwszego elementu partycji.
i_k	– indeks końcowego elementu partycji.
i_sr	– wyznaczona, przypuszczalna pozycja.

Powyższy wzór wyprowadzamy z prostej proporcji. Jeśli zbiór posiada liniowy rozkład elementów, to odległość wartości poszukiwanej k od Z [ i_p ] jest w przybliżeniu proporcjonalna do liczby elementów pomiędzy i_sr a i_p:

i_p

...

i_sr

...

i_k

Z [ i_p ]

...

Z [ i_k ]

Skoro tak, to zachodzi przybliżona proporcja:

, mnożymy obustronnie przez i_k - i_p.

, dodajemy obustronnie i_p.

, zaokrąglamy do wartości całkowitej i otrzymujemy wzór końcowy.

Aby zrozumieć zaletę tego sposobu wyznaczania pozycji, przyjrzyjmy się poniższemu przykładowi, gdzie wyliczyliśmy pozycję wg wzoru z poprzedniego rozdziału oraz wg wzoru podanego powyżej. Poszukiwany element zaznaczono kolorem czerwonym:

nr pozycji =	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
elementy Z =	10	11	13	13	15	16	18	19	20	22	22	23	25	27	27	28	29	30	32
binarnie i_sr =										X
interpolacyjnie i_sr =					X

Binarne wyznaczenie pozycji:

Interpolacyjne wyznaczenie pozycji:

Metoda interpolacyjna wyznacza pozycję zwykle dużo bliżej poszukiwanego elementu niż metoda binarna (w przykładzie trafiamy za pierwszym razem ). Zauważ, iż w metodzie binarnej nie korzystamy zupełnie z wartości elementów na krańcach dzielonej partycji, czyli działamy niejako na ślepo. Natomiast metoda interpolacyjna wyznacza położenie w zależności od wartości elementów zbioru oraz wartości poszukiwanego elementu. Działa zatem celowo dostosowując się do zastanych w zbiorze warunków. Stąd jej dużo większa efektywność.

Po wyznaczeniu położenia i_sr pozostała część algorytmu jest bardzo podobna do wyszukiwania binarnego. Sprawdzamy, czy element na pozycji i_sr posiada poszukiwany klucz k. Jeśli tak, to wyszukiwanie kończy się zwróceniem pozycji i_sr. W przeciwnym razie jeśli k jest mniejsze od klucza elementu Z [ i_sr ], to poszukiwania kontynuujemy w lewej części zbioru od elementu Z [ i_p ] do Z [ i_sr - 1 ]. W przeciwnym razie szukamy w prawej części od Z [ i_sr + 1 ] do Z [ i_k ]. Wyszukiwanie kończy się porażką, jeśli poszukiwany klucz wyjdzie poza przedział <Z [ i_p ], Z [ i_k ]>. W takim przypadku kończymy zwracając jako pozycję liczbę -1.

Wyszukiwanie interpolacyjne posiada klasę czasowej złożoności obliczeniowej równą O ( log log n ), zatem wyszukuje znacząco szybciej w zbiorach o liniowym rozkładzie elementów niż wyszukiwanie binarne o klasie O ( log n ).

Algorytm wyszukiwania interpolacyjnego

Wejście:

i_p	–	indeks pierwszego elementu w tablicy Z, i_p ∈ C.
i_k	–	indeks ostatniego elementu w tablicy Z, i_k ∈ C.
Z	–	tablica do wyszukania elementu. Indeksy od i_p do i_k.
k	–	wartość poszukiwanego elementu – tzw. klucz.

Wyjście:

p = indeks elementu o kluczu k lub
p = -1, jeśli nie odnalezienia elementu o takim kluczu.

Zmienne pomocnicze:

i_sr

–

indeks elementu środkowego. i_sr ∈ C.

Lista kroków:

K01:	p ← -1	zakładamy, iż k nie występuje w zbiorze
K02:	Dopóki Z [ i_p ] ≤ k ≤ Z [ i_k ], wykonuj kroki K02...K10	w pętli poszukujemy elementu o wartości k
K03:		wyznaczamy pozycję elementu interpolowanego
K04:	Jeśli k ≠ Z [ i_sr ], to idź do kroku K07
K05:	p ← i_sr	element znaleziony, kończymy
K06:	Idź do K11
K07:	Jeśli k < Z [ i_sr ], to idź do kroku K10	wybieramy odpowiednią połówkę zbioru na dalsze poszukiwania
K08:	i_p ← i_sr + 1	k > Z [ i_sr ] → druga połówka
K09:	Następny obieg pętli K02
K10:	i_k ← i_sr - 1	k < Z [ i_sr ] → pierwsza połówka
K11:	Zakończ z wynikiem p

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wypełnia tablicę 100 elementową Z liczbami naturalnymi w taki sposób, aby powstał z nich ciąg rosnący. Następnie generuje liczbę pseudolosową k z zakresu od Z [ 0 ] do Z [ 99 ] i wyszukuje interpolacyjnie jej położenia w tablicy. Na koniec wyświetlana jest liczba k, jej położenie w Z oraz zawartość tablicy Z z zaznaczonym elementem o wartości k. Jeśli k nie występuje w Z, to zamiast położenia program wyświetla słowo BRAK. Dodatkowo program zlicza wykonane obiegi pętli i wypisuje ich liczbę.

Pascal

// Wyszukiwanie interpolacyjne
// Data:   8.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 100;

var
  Z : array [ 0..N - 1 ] of integer;
  i, ip, ik, isr, k, L, p : integer;

begin
  randomize;

  // wypełniamy tablicę Z [ ] 

  Z [ 0 ] := random ( 5 );
  for i := 1 to N - 1 do Z [ i ] := Z [ i - 1 ] + random ( 5 );

  // generujemy klucz k

  k := Z [ 0 ] + random ( Z [ N - 1 ] - Z [ 0 ] + 1 );

  // poszukujemy interpolacyjnie elementu k

  L  := 0; p  := -1; ip := 0; ik := N - 1;
  while( Z [ ip ] <= k ) and ( k <= Z [ ik ] ) do
  begin
    inc ( L );
    isr := ip + ( k - Z [ ip ] )* ( ik - ip ) div ( Z [ ik ] - Z [ ip ] );
    if Z [ isr ] = k then
    begin
      p := isr; break;
    end
    else if k < Z [ isr ] then
      ik := isr - 1
    else
      ip := isr + 1;
  end;

  // wyświetlamy wyniki

  write ( k, ': ' );
  if p >= 0 then write ( p ) else write ( 'BRAK' );
  writeln ( ': obiegi = ', L );
  writeln;
  for i := 0 to N - 1 do
  begin
    write ( Z [ i ] :3 );
    if p = i then write ( '<' ) else write ( ' ' );
  end;
  writeln;
  writeln;
end.

C++

// Wyszukiwanie interpolacyjne
// Data:   8.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 100;

int main( )
{
  int Z [ N ], i, ip, ik, isr, k, L, p;

  srand ( ( unsigned )time ( NULL ) );

  // wypełniamy tablicę Z [ ] 

  Z [ 0 ] = rand( ) % 5;
  for( i = 1; i < N; i++ ) Z [ i ] = Z [ i - 1 ] + ( rand( ) % 5 );

  // generujemy klucz k

  k = Z [ 0 ] + ( rand( ) % ( Z [ N - 1 ] - Z [ 0 ] + 1 ) );

  // poszukujemy interpolacyjnie elementu k

  p = -1; L = ip = 0; ik = N - 1;
  while( ( Z [ ip ] <= k ) && ( k <= Z [ ik ] ) )
  {
    L++;
    isr = ip + ( k - Z [ ip ] )* ( ik - ip ) / ( Z [ ik ] - Z [ ip ] );
    if( Z [ isr ] == k )
    {
      p = isr; break;
    }
    else if( k < Z [ isr ] )
      ik = isr - 1;
    else
      ip = isr + 1;
  }

  // wyświetlamy wyniki

  cout << k << ": ";
  if( p >= 0 ) cout << p; else cout << "BRAK";
  cout << ": obiegi = " << L << endl << endl;
  for( i = 0; i < N; i++ )
  {
    cout << setw ( 3 ) << Z [ i ];
    if( p == i ) cout << "<"; else cout << " ";
  }
  cout << endl << endl;
  return 0;
}

Basic

' Wyszukiwanie interpolacyjne
' Data:   8.05.2008
' (C)2020 mgr Jerzy Wałaszek'---------------------------

Const N = 100

Dim As Integer Z ( N-1 ), i, ip, ik, isr, k, L, p

Randomize

' wypełniamy tablicę Z [ ] 

Z ( 0 ) = Cint ( Rnd * 4 )
For i = 1 To N - 1: Z ( i ) = Z ( i-1 ) + Cint ( Rnd * 4 ): Next

' generujemy klucz k

k = Z ( 0 ) + Cint ( Rnd * ( Z ( N - 1 ) - Z ( 0 ) ) )

' poszukujemy interpolacyjnie elementu k

L  = 0: p  = -1: ip = 0: ik = N - 1
while( Z ( ip ) <= k ) And ( k <= Z ( ik ) )
  L += 1
  isr = ip + ( k - Z ( ip ) ) * ( ik - ip ) \ ( Z ( ik ) - Z ( ip ) )
  If Z ( isr ) = k Then
    p = isr: Exit While
  Elseif k < Z ( isr ) Then
    ik = isr - 1
  Else
    ip = isr + 1
  End If
Wend

' wyświetlamy wyniki

Print k;": ";
If p >= 0 Then Print p;: Else Print "BRAK";
Print ": obiegi =";L
Print
For i = 0 To N - 1
  Print Using "###";Z ( i );
  If p = i Then Print "<";: Else Print " ";
Next
Print
Print
End

Wynik:

151 : BRAK : obiegi = 1

4 5 9 12 15 15 15 19 21 24 24 24 25 28 32 33 33 35 39 40
41 43 44 45 47 47 51 54 56 57 58 59 62 64 66 68 69 71 71 72
72 74 77 81 84 87 91 91 95 95 95 99 99 101 103 104 108 111 114 116
117 120 120 122 125 129 130 133 136 139 140 141 145 149 153 155 157 161 164 166
168 170 170 170 171 174 176 177 181 183 183 186 188 191 191 195 195 199 199 201

83 : 44 : obiegi = 2

3 4 6 8 10 10 13 14 14 14 18 18 20 24 24 24 24 25 25 25
26 28 31 33 34 36 36 38 42 42 43 47 51 52 54 55 59 63 63 67
71 75 76 80 83< 86 86 87 90 92 96 98 101 103 103 107 108 111 113 116
119 122 125 128 128 128 128 131 135 139 139 142 142 143 145 149 150 150 152 153
156 160 161 163 164 164 165 168 169 169 169 170 171 172 174 176 176 179 180 184

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Wyszukiwanie interpolacyjne