INTERPOLATIONSSØGNING

Givet et sorteret array af n ensartet fordelte værdier arr[] skriv en funktion til at søge efter et bestemt element x i arrayet.
Lineær søgning finder elementet i O(n) tid Hop Søg tager O(n) tid og Binær søgning tager O(log n) tid.
Interpolationssøgningen er en forbedring i forhold til Binær søgning for tilfælde, hvor værdierne i et sorteret array er ensartet fordelt. Interpolation konstruerer nye datapunkter inden for rækkevidden af et diskret sæt af kendte datapunkter. Binær søgning går altid til det midterste element for at kontrollere. På den anden side kan interpolationssøgning gå til forskellige steder i henhold til værdien af den nøgle, der søges efter. For eksempel hvis værdien af nøglen er tættere på det sidste element, vil interpolationssøgning sandsynligvis starte søgning mod slutningen.
For at finde den position, der skal søges, bruger den følgende formel.

// Ideen med formel er at returnere højere værdi af pos
// når element, der skal søges i, er tættere på arr[hi]. Og
// mindre værdi, når tættere på arr[lo]

arr[] ==> Array, hvor der skal søges i elementer
x ==> Element, der skal søges i
lo ==> Startindeks i arr[]

hej ==> Afsluttende indeks i arr[]
efter = +

Der er mange forskellige interpolationsmetoder, og en sådan er kendt som lineær interpolation. Lineær interpolation tager to datapunkter, som vi antager som (x1y1) og (x2y2), og formlen er: ved punkt(xy).

Denne algoritme fungerer på en måde, vi søger efter et ord i en ordbog. Interpolationssøgealgoritmen forbedrer den binære søgealgoritme. Formlen for at finde en værdi er: K = >K er en konstant, som bruges til at indsnævre søgerummet. I tilfælde af binær søgning er værdien for denne konstant: K=(lav+høj)/2.

Formlen for pos kan udledes som følger.

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])

Algoritme
Resten af interpolationsalgoritmen er den samme bortset fra ovenstående partitionslogik.

Trin 1: Beregn værdien af 'pos' i en løkke ved hjælp af probepositionsformlen.
Trin 2: Hvis det er et match returner indekset for varen og forlad.
Trin 3: Hvis elementet er mindre end arr[pos], beregnes sondepositionen for den venstre sub-array. Ellers beregn det samme i højre sub-array.
Trin 4: Gentag indtil et match er fundet, eller sub-arrayet reduceres til nul.

Nedenfor er implementeringen af algoritmen.

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

Produktion

Element found at index 4

Tidskompleksitet: O(log₂(log₂n)) for det gennemsnitlige tilfælde og O(n) for det værste tilfælde
Ekstra rumkompleksitet: O(1)

En anden tilgang: -

Dette er iterationstilgangen til interpolationssøgningen.

Trin 1: Beregn værdien af 'pos' i en løkke ved hjælp af probepositionsformlen.
Trin 2: Hvis det er et match returner indekset for varen og forlad.
Trin 3: Hvis elementet er mindre end arr[pos], beregnes sondepositionen for den venstre sub-array. Ellers beregn det samme i højre sub-array.
Trin 4: Gentag indtil et match er fundet, eller sub-arrayet reduceres til nul.