Интерполационно търсене
Даден е сортиран масив от 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 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 ?>
Изход
Element found at index 4
Времева сложност: O(дневник 2 (дневник 2 n)) за средния случай и O(n) за най-лошия случай
Сложност на спомагателното пространство: О(1)
Друг подход: -
Това е итерационният подход за интерполационно търсене.
- Стъпка 1: В цикъл изчислете стойността на 'pos', като използвате формулата за позиция на сондата.
- Стъпка 2: Ако е съвпадение, върнете индекса на елемента и излезте.
- Стъпка 3: Ако елементът е по-малък от arr[pos], изчислете позицията на сондата на левия подмасив. В противен случай изчислете същото в десния подмасив.
- Стъпка 4: Повторете, докато се намери съвпадение или подмасивът се намали до нула.
По-долу е изпълнението на алгоритъма.
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' ); }
Изход
Element found at index 4
Времева сложност: O(log2(log2 n)) за средния случай и O(n) за най-лошия случай
Сложност на спомагателното пространство: О(1)
