logo

TechCodeview

Wyszukiwanie interpolacyjne

Mając posortowaną tablicę n równomiernie rozłożonych wartości arr[], napisz funkcję, która wyszuka określony element x w tablicy. 
Wyszukiwanie liniowe znajduje element w czasie O(n). Przeskocz wyszukiwanie zajmuje czas O(n) i Wyszukiwanie binarne zajmuje czas O(log n). 
Wyszukiwanie interpolacyjne jest ulepszeniem w stosunku do Wyszukiwanie binarne na przykład, gdy wartości w posortowanej tablicy są równomiernie rozłożone. Interpolacja konstruuje nowe punkty danych w zakresie dyskretnego zestawu znanych punktów danych. Wyszukiwanie binarne zawsze sprawdza środkowy element. Z drugiej strony wyszukiwanie interpolacyjne może odbywać się w różnych lokalizacjach w zależności od wartości przeszukiwanego klucza. Na przykład, jeśli wartość klucza jest bliższa ostatniemu elementowi, wyszukiwanie interpolacyjne prawdopodobnie rozpocznie się w kierunku końca.
Aby znaleźć stanowisko, które ma być przeszukane, posługuje się następującym wzorem. 

// Ideą formuły jest zwrócenie wyższej wartości poz
// gdy przeszukiwany element jest bliżej arr[hi]. I
// mniejsza wartość, gdy jest bliżej arr[lo]



Linux edytuj plik

arr[] ==> Tablica, w której należy przeszukać elementy

x     ==> Element do przeszukania

lo    ==> Indeks początkowy w arr[]



cześć    ==> Indeks końcowy w arr[]

po = +               

Istnieje wiele różnych metod interpolacji, a jedna z nich nazywa się interpolacją liniową. Interpolacja liniowa uwzględnia dwa punkty danych, które zakładamy jako (x1y1) i (x2y2), a wzór wygląda następująco:  w punkcie (xy).



Algorytm ten działa w taki sposób, że wyszukujemy słowo w słowniku. Algorytm wyszukiwania interpolacyjnego ulepsza algorytm wyszukiwania binarnego.  Wzór na znalezienie wartości jest następujący: K = >K jest stałą używaną do zawężania przestrzeni poszukiwań. W przypadku wyszukiwania binarnego wartość tej stałej wynosi: K=(niska+wysoka)/2.

sprawić, że skrypt powłoki będzie wykonywalny

  

Wzór na poz można wyprowadzić w następujący sposób. 

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

Algorytm  
Reszta algorytmu interpolacji jest taka sama, z wyjątkiem powyższej logiki podziału. 

  • Krok 1: W pętli oblicz wartość „pos” za pomocą wzoru na położenie sondy. 
  • Krok 2: Jeśli jest to dopasowanie, zwróć indeks elementu i wyjdź. 
  • Krok 3: Jeśli element jest mniejszy niż arr[pos], oblicz pozycję sondy lewej podtablicy. W przeciwnym razie oblicz to samo w prawej podtablicy. 
  • Krok 4: Powtarzaj, aż zostanie znalezione dopasowanie lub tablica podrzędna zmniejszy się do zera.


Poniżej implementacja algorytmu. 

Różnica dat w Excelu
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 
// 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# 
// 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 ?>

Wyjście 
Element found at index 4

Złożoność czasowa: O(log2(dziennik2n)) dla przypadku przeciętnego i O(n) dla przypadku najgorszego 
Złożoność przestrzeni pomocniczej: O(1)

Inne podejście: -

Jest to podejście iteracyjne do wyszukiwania interpolacyjnego.

  • Krok 1: W pętli oblicz wartość „pos” za pomocą wzoru na położenie sondy. 
  • Krok 2: Jeśli jest to dopasowanie, zwróć indeks elementu i wyjdź. 
  • Krok 3: Jeśli element jest mniejszy niż arr[pos], oblicz pozycję sondy lewej podtablicy. W przeciwnym razie oblicz to samo w prawej podtablicy. 
  • Krok 4: Powtarzaj, aż zostanie znalezione dopasowanie lub tablica podrzędna zmniejszy się do zera.

Poniżej implementacja algorytmu. 

C++ 
// C++ program to implement interpolation search by using iteration approach #include   using namespace std;   int interpolationSearch(int arr[] int n int x) {  // Find indexes of two corners  int low = 0 high = (n - 1);  // Since array is sorted an element present  // in array must be in range defined by corner  while (low <= high && x >= arr[low] && x <= arr[high])  {  if (low == high)  {if (arr[low] == x) return low;  return -1;  }  // Probing the position with keeping  // uniform distribution in mind.  int pos = low + (((double)(high - low) /  (arr[high] - arr[low])) * (x - arr[low]));    // Condition of target found  if (arr[pos] == x)  return pos;  // If x is larger x is in upper part  if (arr[pos] < x)  low = pos + 1;  // If x is smaller x is in the lower part  else  high = pos - 1;  }  return -1; }   // Main function int main() {  // Array of items on whighch 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 n x);    // If element was found  if (index != -1)  cout << 'Element found at index ' << index;  else  cout << 'Element not found.';  return 0; }  //this code contributed by Ajay Singh
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;  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.');  } }
Python 
# Python equivalent of above C++ code  # Python program to implement interpolation search by using iteration approach def interpolationSearch(arr n x): # Find indexes of two corners  low = 0 high = (n - 1) # Since array is sorted an element present  # in array must be in range defined by corner  while low <= high and x >= arr[low] and x <= arr[high]: if low == high: if arr[low] == x: return low; return -1; # Probing the position with keeping  # uniform distribution in mind.  pos = int(low + (((float(high - low)/( arr[high] - arr[low])) * (x - arr[low])))) # Condition of target found  if arr[pos] == x: return pos # If x is larger x is in upper part  if arr[pos] < x: low = pos + 1; # If x is smaller x is in lower part  else: high = pos - 1; return -1 # Main function if __name__ == '__main__': # Array of items on whighch search will  # be conducted. arr = [10 12 13 16 18 19 20 21 22 23 24 33 35 42 47] n = len(arr) x = 18 # Element to be searched index = interpolationSearch(arr n x) # If element was found if index != -1: print ('Element found at index'index) else: print ('Element not found')
C# 
// C# program to implement interpolation search by using // iteration approach using System; class Program {  // Interpolation Search function  static int InterpolationSearch(int[] arr int n int x)  {  int low = 0;  int high = n - 1;    while (low <= high && x >= arr[low] && x <= arr[high])   {  if (low == high)   {  if (arr[low] == x)   return low;   return -1;   }    int pos = low + (int)(((float)(high - low) / (arr[high] - arr[low])) * (x - arr[low]));    if (arr[pos] == x)   return pos;     if (arr[pos] < x)   low = pos + 1;     else   high = pos - 1;   }    return -1;  }    // Main function  static void Main(string[] args)  {  int[] arr = {10 12 13 16 18 19 20 21 22 23 24 33 35 42 47};  int n = arr.Length;    int x = 18;  int index = InterpolationSearch(arr n x);    if (index != -1)   Console.WriteLine('Element found at index ' + index);  else   Console.WriteLine('Element not found');  } } // This code is contributed by Susobhan Akhuli
JavaScript 
// JavaScript program to implement interpolation search by using iteration approach function interpolationSearch(arr n x) { // Find indexes of two corners let low = 0; let high = n - 1; // Since array is sorted an element present // in array must be in range defined by corner while (low <= high && x >= arr[low] && x <= arr[high]) {  if (low == high) {  if (arr[low] == x) {  return low;  }  return -1;  }  // Probing the position with keeping  // uniform distribution in mind.  let pos = Math.floor(low + (((high - low) / (arr[high] - arr[low])) * (x - arr[low])));  // Condition of target found  if (arr[pos] == x) {  return pos;  }  // If x is larger x is in upper part  if (arr[pos] < x) {  low = pos + 1;  }  // If x is smaller x is in lower part  else {  high = pos - 1;  } } return -1; } // Main function let arr = [10 12 13 16 18 19 20 21 22 23 24 33 35 42 47]; let n = arr.length; let x = 18; // Element to be searched let index = interpolationSearch(arr n x); // If element was found if (index != -1) { console.log('Element found at index' index); } else { console.log('Element not found'); }

Wyjście 
Element found at index 4

Złożoność czasowa: O(log2(log2 n)) dla przypadku przeciętnego i O(n) dla przypadku najgorszego 
Złożoność przestrzeni pomocniczej: O(1)