// 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.

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

' 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

# Wyszukiwanie interpolacyjne
# Data: 27.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 100
z = [random.randrange(5)]

# wypełniamy tablicę Z[]
for i in range(N):
    z.append(z[i]+random.randrange(5))

# generujemy klucz k
k = random.randrange(z[0], z[N-1]+1)

# poszukujemy interpolacyjnie elementu k
c, p, ip, ik = 0, -1, 0, N-1
while(z[ip] <= k) and (k <= z[ik]):
    c += 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 =", c)
print()
for i in range(N):
    print("%3d" % z[i], end="")
    if p == i:
        print("<", end="")
    else:
        print(" ", end="")
print()
print()