INTERPOLĀCIJAS MEKLĒŠANA

Dots sakārtots n vienmērīgi sadalītu vērtību masīvs arr[] ierakstiet funkciju, lai masīvā meklētu noteiktu elementu x.
Lineārā meklēšana atrod elementu O(n) laikā Pārlēkt meklēšanu aizņem O(n) laiku un Binārā meklēšana aizņem O(log n) laiku.
Interpolācijas meklēšana ir uzlabojums salīdzinājumā ar Binārā meklēšana gadījumiem, kad sakārtotā masīvā vērtības ir vienmērīgi sadalītas. Interpolācija konstruē jaunus datu punktus zināmu datu punktu diskrētas kopas diapazonā. Binārā meklēšana vienmēr pāriet uz vidējo elementu, lai pārbaudītu. No otras puses, interpolācijas meklēšana var notikt dažādās vietās atkarībā no meklējamās atslēgas vērtības. Piemēram, ja atslēgas vērtība ir tuvāk pēdējam elementam, interpolācijas meklēšana, visticamāk, sāks meklēšanu beigu pusē.
Lai atrastu meklējamo pozīciju, tā izmanto šādu formulu.

// Formulas ideja ir atgriezt augstāku pozīcijas vērtību
// kad meklējamais elements ir tuvāk arr[hi]. Un
// mazāka vērtība, kad tuvāk arr[lo]

arr[] ==> Masīvs, kurā elementi ir jāmeklē
x ==> Meklējamais elements
lo ==> Sākuma indekss arr[]

sveiki ==> Beigu rādītājs arr[]
Linux kā pārdēvēt direktoriju
pēc = +

Ir daudz dažādu interpolācijas metožu, un viena no tām ir pazīstama kā lineārā interpolācija. Lineārajai interpolācijai ir nepieciešami divi datu punkti, kurus mēs pieņemam kā (x1y1) un (x2y2), un formula ir: punktā (xy).

Šis algoritms darbojas tādā veidā, kā mēs meklējam vārdu vārdnīcā. Interpolācijas meklēšanas algoritms uzlabo bināro meklēšanas algoritmu. Formula vērtības atrašanai ir: K = >K ir konstante, ko izmanto, lai sašaurinātu meklēšanas telpu. Binārās meklēšanas gadījumā šīs konstantes vērtība ir: K=(zema+augsta)/2.

Pos formulu var iegūt šādi.

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

Algoritms
Pārējais interpolācijas algoritms ir tāds pats, izņemot iepriekš minēto nodalījuma loģiku.

1. darbība: Ciklā aprēķina 'pos' vērtību, izmantojot zondes pozīcijas formulu.
2. darbība: Ja tā ir sakritība, atgrieziet preces indeksu un izejiet.
3. darbība: Ja vienums ir mazāks par arr[pos], aprēķina kreisā apakšmasīva zondes pozīciju. Pretējā gadījumā aprēķiniet to pašu labajā apakšmasīvā.
4. darbība: Atkārtojiet, līdz tiek atrasta atbilstība vai apakšmasīvs samazinās līdz nullei.

Zemāk ir algoritma ieviešana.

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

Izvade

Element found at index 4

Laika sarežģītība: O(log₂(log₂n)) vidējam gadījumam un O(n) sliktākajam gadījumam
Papildu telpu sarežģītība: O(1)

Cita pieeja:

Šī ir iterācijas pieeja interpolācijas meklēšanai.

1. darbība: Ciklā aprēķina 'pos' vērtību, izmantojot zondes pozīcijas formulu.
2. darbība: Ja tā ir sakritība, atgrieziet preces indeksu un izejiet.
3. darbība: Ja vienums ir mazāks par arr[pos], aprēķina kreisā apakšmasīva zondes pozīciju. Pretējā gadījumā aprēķiniet to pašu labajā apakšmasīvā.
4. darbība: Atkārtojiet, līdz tiek atrasta atbilstība vai apakšmasīvs samazinās līdz nullei.