Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie interpolacyjne

SPIS TREŚCI
Tematy pomocnicze

Problem

W zbiorze Z uporządkowanym rosnąco należy wyszukać element o wartości (o kluczu) k.

Rozwiązanie

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ść.
ip : indeks pierwszego elementu partycji.
ik : indeks końcowego elementu partycji.
isr : 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[ip] jest w przybliżeniu proporcjonalna do liczby elementów pomiędzy isrip:

ip isr         ik
Z[ip] k         Z[ik]

Skoro tak, to zachodzi przybliżona proporcja:

, mnożymy obustronnie przez ik-ip.
, dodajemy obustronnie ip.
, 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 isr =
 
 
 
 
 
 
 
 
 
X
 
 
 
 
 
 
 
 
 
interpolacyjnie isr =
 
 
 
 
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 isr pozostała część algorytmu jest bardzo podobna do wyszukiwania binarnego. Sprawdzamy, czy element na pozycji isr posiada poszukiwany klucz k. Jeśli tak, to wyszukiwanie kończy się zwróceniem pozycji isr. W przeciwnym razie jeśli k jest mniejsze od klucza elementu Z[isr], to poszukiwania kontynuujemy w lewej części zbioru od elementu Z[ip] do Z[isr - 1]. W przeciwnym razie szukamy w prawej części od Z[isr + 1] do Z [ik]. Wyszukiwanie kończy się porażką, jeśli poszukiwany klucz wyjdzie poza przedział <Z[ip], Z[ik>. 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:

ip : indeks pierwszego elementu w tablicy Z. ip ∈ C.
ik : indeks ostatniego elementu w tablicy Z. ik ∈ C.
Z : tablica do wyszukania elementu. Indeksy od ip do ik.
k : wartość poszukiwanego elementu – tzw. klucz.

Wyjście:

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

Zmienne pomocnicze:

isr : indeks elementu środkowego. isr ∈ C.

Lista kroków:

K01: p ← -1 ; zakładamy, iż k nie występuje w zbiorze
K02: Dopóki Z[ip] ≤ kZ[ik], ; w pętli poszukujemy 
     wykonuj kroki K02…K10     ; elementu o wartości k
K03:   isrip+[(k-Z[ip])·(ik-ip)/(Z[ik]-Z[ip])] ; wyznaczamy pozycję
                                                ; elementu interpolowanego
K04:   Jeśli kZ[isr],
       to idź do kroku K07
K05:   p ← isr ; element znaleziony, kończymy
K06:   Idź do K11
K07:   Jeśli k < Z[isr],   ; wybieramy odpowiednią połówkę
       to idź do kroku K10 ; zbioru na dalsze poszukiwania
K08:   ip ← isr + 1 ; k > Z[isr] → druga połówka
K09:   Następny obieg pętli K02
K10:   ik ← isr - 1 ; k < Z[isr] → 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 <ctime>

using namespace std;

const int N = 100;

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

  srand(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
Python (dodatek)
# Wyszukiwanie interpolacyjne
# Data: 27.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 100
Z = []

# wypełniamy tablicę Z[]

Z.append(random.randrange(5))
for i in range(1,N):
    Z.append(Z[i-1]+random.randrange(5))

# generujemy klucz k

k = random.randrange(Z[0],Z[N-1]+1)

# poszukujemy interpolacyjnie elementu k

L,p,ip,ik = 0,-1,0,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:
        p = isr
        break
    elif k < Z[isr]:
        ik = isr - 1
    else:
        ip = isr + 1

# wyświetlamy wyniki

print(k,": ",end="")
if p >= 0:
    print(p,end="")
else:
    print("BRAK",end="")
print(" : obiegi =",L)
print()
for i in range(N):
    print("%3d" % Z[i],end="")
    if p == i:
        print("<",end="")
    else:
        print(" ",end="")
print()
print()
Wynik:
163 : BRAK : obiegi = 4

   4   7   7  11  11  13  16  18  20  22  23  26  27  30  32  36  39  40  41  41
  42  45  46  47  50  50  53  54  58  59  60  61  64  67  70  73  77  80  80  84
  88  89  92  93  95  99 102 105 108 108 108 108 111 112 112 112 116 117 117 119
 120 124 126 129 133 133 136 138 139 140 141 144 148 151 152 153 154 155 158 160
 161 161 162 162 162 164 165 168 171 171 174 175 178 179 183 185 188 192 192 196

131  : 67 : obiegi = 3

   4   8  12  15  17  17  18  18  18  18  19  20  20  20  22  26  28  31  31  34
  35  37  39  42  46  48  52  55  58  60  61  62  62  66  67  67  68  69  70  70
  71  72  74  74  77  81  82  86  88  92  96  96  97  99  99 103 105 108 111 114
 115 116 120 121 123 124 127 131<132 136 140 142 144 145 148 152 156 158 161 163
 167 171 171 174 178 182 185 187 189 191 195 195 195 199 202 203 204 208 208 209

Wyszukiwanie interpolacyjne
(C)2020 mgr Jerzy Wałaszek


Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.