ІНТЕРПОЛЯЦІЙНИЙ ПОШУК

Дано відсортований масив із n рівномірно розподілених значень arr[], напишіть функцію для пошуку певного елемента x у масиві.
Лінійний пошук знаходить елемент за O(n) часу Перейти до пошуку займає O(n) часу і Двійковий пошук займає O(log n) часу.
Інтерполяційний пошук є вдосконаленням Двійковий пошук наприклад, коли значення в сортованому масиві рівномірно розподілені. Інтерполяція створює нові точки даних у діапазоні дискретного набору відомих точок даних. Двійковий пошук завжди переходить до середнього елемента для перевірки. З іншого боку, інтерполяційний пошук може здійснюватися в різних місцях відповідно до значення шуканого ключа. Наприклад, якщо значення ключа ближче до останнього елемента, інтерполяційний пошук, швидше за все, розпочне пошук у напрямку до кінця.
Щоб знайти позицію для пошуку, використовується наступна формула.

// Ідея формули полягає в тому, щоб повернути більше значення позиції
// коли шуканий елемент ближче до arr[hi]. І
// менше значення, коли ближче до arr[lo]

arr[] ==> Масив, де елементи потрібно шукати
x ==> Елемент для пошуку
lo ==> Початковий індекс в arr[]

привіт ==> Кінцевий індекс в arr[]
після = +

Існує багато різних методів інтерполяції, і один із них відомий як лінійна інтерполяція. Лінійна інтерполяція використовує дві точки даних, які ми припускаємо як (x1y1) і (x2y2), а формула така: у точці (xy).

Цей алгоритм працює так, як ми шукаємо слово в словнику. Алгоритм інтерполяції покращує бінарний алгоритм пошуку. Формула для знаходження значення: K = >K — константа, яка використовується для звуження простору пошуку. У випадку двійкового пошуку значення цієї константи таке: K=(низький+високий)/2.

Формула для pos може бути отримана наступним чином.

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

Алгоритм
Решта алгоритму інтерполяції така ж, за винятком вищевказаної логіки розділення.

Крок 1: У циклі обчисліть значення 'pos' за допомогою формули положення зонда.
Крок 2: Якщо це збіг, поверніть індекс елемента та вийдіть.
крок 3: Якщо елемент менший за arr[pos], обчисліть позицію зонда лівого підмасиву. В іншому випадку обчисліть те саме в правому підмасиві.
крок 4: Повторюйте, доки не буде знайдено збіг або підмасив не зменшиться до нуля.

Нижче представлена реалізація алгоритму.

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

Вихід

Element found at index 4

Часова складність: O(log₂(журнал₂n)) для середнього випадку та O(n) для гіршого випадку
Складність допоміжного простору: О(1)

Інший підхід: -

Це ітераційний підхід для інтерполяційного пошуку.

Крок 1: У циклі обчисліть значення 'pos' за допомогою формули положення зонда.
Крок 2: Якщо це збіг, поверніть індекс елемента та вийдіть.
крок 3: Якщо елемент менший за arr[pos], обчисліть позицію зонда лівого підмасиву. В іншому випадку обчисліть те саме в правому підмасиві.
крок 4: Повторюйте, доки не буде знайдено збіг або підмасив не зменшиться до нуля.