INTERPOLAATIOHAKU

Kun annetaan n tasaisesti jakautuneen arvon lajiteltu taulukko, arr[] kirjoita funktio, joka etsii tiettyä elementtiä x taulukosta.
Lineaarinen haku löytää elementin O(n) ajassa Jump Search kestää O(n) aikaa ja Binäärihaku kestää O(log n) aikaa.
Interpolaatiohaku on parannus verrattuna Binäärihaku tapauksia, joissa lajitellun taulukon arvot jakautuvat tasaisesti. Interpolointi rakentaa uusia datapisteitä tunnettujen tietopisteiden diskreetin joukon alueelle. Binäärihaku menee aina keskimmäiseen elementtiin tarkistaakseen. Toisaalta interpolaatiohaku voi mennä eri paikkoihin haettavan avaimen arvon mukaan. Esimerkiksi jos avaimen arvo on lähempänä viimeistä elementtiä, interpolointihaku aloittaa todennäköisesti haun loppupuolella.
Etsittävän paikan löytämiseksi se käyttää seuraavaa kaavaa.

// Kaavan ideana on palauttaa suurempi pos-arvo
// kun haettava elementti on lähempänä arr[hi]. Ja
// pienempi arvo, kun lähempänä arr[lo]

arr[] ==> Taulukko, josta elementtejä täytyy etsiä
x ==> Haettava elementti
lo ==> Aloitusindeksi arr[]

hei ==> Päättyy hakemistoon arr[]
jälkeen = +

On olemassa monia erilaisia interpolointimenetelmiä, joista yksi tunnetaan lineaarisena interpolaationa. Lineaarinen interpolointi ottaa kaksi datapistettä, jotka oletamme muotoina (x1y1) ja (x2y2), ja kaava on: pisteessä(xy).

komento chown

Tämä algoritmi toimii tavalla, jolla etsimme sanaa sanakirjasta. Interpolaatiohakualgoritmi parantaa binaarihakualgoritmia. Kaava arvon löytämiseksi on: K = >K on vakio, jota käytetään kaventamaan hakuavaruutta. Binäärihaun tapauksessa tämän vakion arvo on: K=(matala+korkea)/2.

Pos:n kaava voidaan johtaa seuraavasti.

Let's assume that the elements of the array are linearly distributed.   
  
General equation of line : y = m*x + c.  
y is the value in the array and x is its index.  
  
Now putting value of lohi and x in the equation  
arr[hi] = m*hi+c ----(1)  
arr[lo] = m*lo+c ----(2)  
x = m*pos + c ----(3)  
  
m = (arr[hi] - arr[lo] )/ (hi - lo)  
  
subtracting eqxn (2) from (3)  
x - arr[lo] = m * (pos - lo)  
lo + (x - arr[lo])/m = pos  
pos = lo + (x - arr[lo]) *(hi - lo)/(arr[hi] - arr[lo])

Algoritmi
Interpolointialgoritmin loppuosa on sama paitsi yllä oleva osiologiikka.

Vaihe 1: Laske silmukassa 'pos':n arvo käyttämällä anturin sijaintikaavaa.
Vaihe2: Jos se täsmää, palauta kohteen indeksi ja poistu.
Vaihe 3: Jos kohde on pienempi kuin arr[pos], laske vasemman alitaulukon mittauspaikka. Muussa tapauksessa laske sama oikeasta alitaulukosta.
Vaihe 4: Toista, kunnes vastaavuus löytyy tai alitaulukko pienenee nollaan.

Alla on algoritmin toteutus.

C++

// C++ program to implement interpolation // search with recursion #include    using namespace std; // If x is present in arr[0..n-1] then returns // index of it else returns -1. int interpolationSearch(int arr[] int lo int hi int x) {  int pos;  // Since array is sorted an element present  // in array must be in range defined by corner  if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {  // Probing the position with keeping  // uniform distribution in mind.  pos = lo  + (((double)(hi - lo) / (arr[hi] - arr[lo]))  * (x - arr[lo]));  // Condition of target found  if (arr[pos] == x)  return pos;  // If x is larger x is in right sub array  if (arr[pos] < x)  return interpolationSearch(arr pos + 1 hi x);  // If x is smaller x is in left sub array  if (arr[pos] > x)  return interpolationSearch(arr lo pos - 1 x);  }  return -1; } // Driver Code int main() {  // Array of items on which search will  // be conducted.  int arr[] = { 10 12 13 16 18 19 20 21  22 23 24 33 35 42 47 };  int n = sizeof(arr) / sizeof(arr[0]);  // Element to be searched  int x = 18;  int index = interpolationSearch(arr 0 n - 1 x);  // If element was found  if (index != -1)  cout << 'Element found at index ' << index;  else  cout << 'Element not found.';  return 0; } // This code is contributed by equbalzeeshan

// C program to implement interpolation search // with recursion #include  // If x is present in arr[0..n-1] then returns // index of it else returns -1. int interpolationSearch(int arr[] int lo int hi int x) {  int pos;  // Since array is sorted an element present  // in array must be in range defined by corner  if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {  // Probing the position with keeping  // uniform distribution in mind.  pos = lo  + (((double)(hi - lo) / (arr[hi] - arr[lo]))  * (x - arr[lo]));  // Condition of target found  if (arr[pos] == x)  return pos;  // If x is larger x is in right sub array  if (arr[pos] < x)  return interpolationSearch(arr pos + 1 hi x);  // If x is smaller x is in left sub array  if (arr[pos] > x)  return interpolationSearch(arr lo pos - 1 x);  }  return -1; } // Driver Code int main() {  // Array of items on which search will  // be conducted.  int arr[] = { 10 12 13 16 18 19 20 21  22 23 24 33 35 42 47 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 18; // Element to be searched  int index = interpolationSearch(arr 0 n - 1 x);  // If element was found  if (index != -1)  printf('Element found at index %d' index);  else  printf('Element not found.');  return 0; }

Java

// Java program to implement interpolation // search with recursion import java.util.*; class GFG {  // If x is present in arr[0..n-1] then returns  // index of it else returns -1.  public static int interpolationSearch(int arr[] int lo  int hi int x)  {  int pos;  // Since array is sorted an element  // present in array must be in range  // defined by corner  if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {  // Probing the position with keeping  // uniform distribution in mind.  pos = lo  + (((hi - lo) / (arr[hi] - arr[lo]))  * (x - arr[lo]));  // Condition of target found  if (arr[pos] == x)  return pos;  // If x is larger x is in right sub array  if (arr[pos] < x)  return interpolationSearch(arr pos + 1 hi  x);  // If x is smaller x is in left sub array  if (arr[pos] > x)  return interpolationSearch(arr lo pos - 1  x);  }  return -1;  }  // Driver Code  public static void main(String[] args)  {  // Array of items on which search will  // be conducted.  int arr[] = { 10 12 13 16 18 19 20 21  22 23 24 33 35 42 47 };  int n = arr.length;  // Element to be searched  int x = 18;  int index = interpolationSearch(arr 0 n - 1 x);  // If element was found  if (index != -1)  System.out.println('Element found at index '  + index);  else  System.out.println('Element not found.');  } } // This code is contributed by equbalzeeshan

Python

# Python3 program to implement # interpolation search # with recursion # If x is present in arr[0..n-1] then # returns index of it else returns -1. def interpolationSearch(arr lo hi x): # Since array is sorted an element present # in array must be in range defined by corner if (lo <= hi and x >= arr[lo] and x <= arr[hi]): # Probing the position with keeping # uniform distribution in mind. pos = lo + ((hi - lo) // (arr[hi] - arr[lo]) * (x - arr[lo])) # Condition of target found if arr[pos] == x: return pos # If x is larger x is in right subarray if arr[pos] < x: return interpolationSearch(arr pos + 1 hi x) # If x is smaller x is in left subarray if arr[pos] > x: return interpolationSearch(arr lo pos - 1 x) return -1 # Driver code # Array of items in which # search will be conducted arr = [10 12 13 16 18 19 20 21 22 23 24 33 35 42 47] n = len(arr) # Element to be searched x = 18 index = interpolationSearch(arr 0 n - 1 x) if index != -1: print('Element found at index' index) else: print('Element not found') # This code is contributed by Hardik Jain

// C# program to implement  // interpolation search using System; class GFG{ // If x is present in  // arr[0..n-1] then  // returns index of it  // else returns -1. static int interpolationSearch(int []arr int lo   int hi int x) {  int pos;    // Since array is sorted an element  // present in array must be in range  // defined by corner  if (lo <= hi && x >= arr[lo] &&   x <= arr[hi])  {    // Probing the position   // with keeping uniform   // distribution in mind.  pos = lo + (((hi - lo) /   (arr[hi] - arr[lo])) *   (x - arr[lo]));  // Condition of   // target found  if(arr[pos] == x)   return pos;     // If x is larger x is in right sub array   if(arr[pos] < x)   return interpolationSearch(arr pos + 1  hi x);     // If x is smaller x is in left sub array   if(arr[pos] > x)   return interpolationSearch(arr lo   pos - 1 x);   }   return -1; } // Driver Code  public static void Main()  {    // Array of items on which search will   // be conducted.   int []arr = new int[]{ 10 12 13 16 18   19 20 21 22 23   24 33 35 42 47 };    // Element to be searched   int x = 18;   int n = arr.Length;  int index = interpolationSearch(arr 0 n - 1 x);    // If element was found  if (index != -1)  Console.WriteLine('Element found at index ' +   index);  else  Console.WriteLine('Element not found.'); } } // This code is contributed by equbalzeeshan

JavaScript

<script> // Javascript program to implement Interpolation Search // If x is present in arr[0..n-1] then returns // index of it else returns -1. function interpolationSearch(arr lo hi x){  let pos;    // Since array is sorted an element present  // in array must be in range defined by corner    if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {    // Probing the position with keeping  // uniform distribution in mind.  pos = lo + Math.floor(((hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));;    // Condition of target found  if (arr[pos] == x){  return pos;  }    // If x is larger x is in right sub array  if (arr[pos] < x){  return interpolationSearch(arr pos + 1 hi x);  }    // If x is smaller x is in left sub array  if (arr[pos] > x){  return interpolationSearch(arr lo pos - 1 x);  }  }  return -1; } // Driver Code let arr = [10 12 13 16 18 19 20 21   22 23 24 33 35 42 47]; let n = arr.length; // Element to be searched let x = 18 let index = interpolationSearch(arr 0 n - 1 x); // If element was found if (index != -1){  document.write(`Element found at index ${index}`) }else{  document.write('Element not found'); } // This code is contributed by _saurabh_jaiswal </script>

PHP

 // PHP program to implement $erpolation search // with recursion // If x is present in arr[0..n-1] then returns // index of it else returns -1. function interpolationSearch($arr $lo $hi $x) { // Since array is sorted an element present // in array must be in range defined by corner if ($lo <= $hi && $x >= $arr[$lo] && $x <= $arr[$hi]) { // Probing the position with keeping // uniform distribution in mind. $pos = (int)($lo + (((double)($hi - $lo) / ($arr[$hi] - $arr[$lo])) * ($x - $arr[$lo]))); // Condition of target found if ($arr[$pos] == $x) return $pos; // If x is larger x is in right sub array if ($arr[$pos] < $x) return interpolationSearch($arr $pos + 1 $hi $x); // If x is smaller x is in left sub array if ($arr[$pos] > $x) return interpolationSearch($arr $lo $pos - 1 $x); } return -1; } // Driver Code // Array of items on which search will // be conducted. $arr = array(10 12 13 16 18 19 20 21 22 23 24 33 35 42 47); $n = sizeof($arr); $x = 47; // Element to be searched $index = interpolationSearch($arr 0 $n - 1 $x); // If element was found if ($index != -1) echo 'Element found at index '.$index; else echo 'Element not found.'; return 0; #This code is contributed by Susobhan Akhuli ?>

Lähtö

Element found at index 4

Aika monimutkaisuus: O(log₂(loki₂n)) keskimääräiselle tapaukselle ja O(n) huonoimmalle tapaukselle
Aputilan monimutkaisuus: O(1)

Toinen lähestymistapa:

Tämä on iteraatiomenetelmä interpolaatiohakuun.

Vaihe 1: Laske silmukassa 'pos':n arvo käyttämällä anturin sijaintikaavaa.
Vaihe2: Jos se täsmää, palauta kohteen indeksi ja poistu.
Vaihe 3: Jos kohde on pienempi kuin arr[pos], laske vasemman alitaulukon mittauspaikka. Muussa tapauksessa laske sama oikeasta alitaulukosta.
Vaihe 4: Toista, kunnes vastaavuus löytyy tai alitaulukko pienenee nollaan.