Даден е сортиран масив от n равномерно разпределени стойности arr[], напишете функция за търсене на определен елемент x в масива.
Линейното търсене намира елемента за O(n) време Прескачане на търсене отнема O(n) време и Двоично търсене отнема O(log n) време.
Интерполационното търсене е подобрение в сравнение с Двоично търсене за случаи, когато стойностите в сортиран масив са равномерно разпределени. Интерполацията конструира нови точки от данни в обхвата на дискретен набор от известни точки от данни. Двоичното търсене винаги отива до средния елемент за проверка. От друга страна търсенето с интерполация може да отиде на различни места според стойността на ключа, който се търси. Например, ако стойността на ключа е по-близо до последния елемент, търсенето на интерполация вероятно ще започне търсене към крайната страна.
За да намерите позицията за търсене, тя използва следната формула.
// Идеята на формулата е да върне по-висока стойност на pos
// когато елементът за търсене е по-близо до 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++ program to implement interpolation // search with recursion #include
// C program to implement interpolation search // with recursion #include
// 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
# 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
<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 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(дневник2(дневник2n)) за средния случай и O(n) за най-лошия случай
Сложност на спомагателното пространство: О(1)
Друг подход: -
Това е итерационният подход за интерполационно търсене.
- Стъпка 1: В цикъл изчислете стойността на 'pos', като използвате формулата за позиция на сондата.
- Стъпка 2: Ако е съвпадение, върнете индекса на елемента и излезте.
- Стъпка 3: Ако елементът е по-малък от arr[pos], изчислете позицията на сондата на левия подмасив. В противен случай изчислете същото в десния подмасив.
- Стъпка 4: Повторете, докато се намери съвпадение или подмасивът се намали до нула.
По-долу е изпълнението на алгоритъма.
C++// C++ program to implement interpolation search by using iteration approach #include
// 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 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# 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 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'); }
Изход
Element found at index 4
Времева сложност: O(log2(log2 n)) за средния случай и O(n) за най-лошия случай
Сложност на спомагателното пространство: О(1)