Cerca per interpolació
Donada una matriu ordenada de n valors distribuïts uniformement arr[], escriviu una funció per cercar un element x concret a la matriu.
La cerca lineal troba l'element en temps O(n). Salt de cerca triga O(n) temps i Cerca binària triga O(log n) temps.
La cerca d'interpolació és una millora Cerca binària per als casos en què els valors d'una matriu ordenada es distribueixen uniformement. La interpolació construeix nous punts de dades dins del rang d'un conjunt discret de punts de dades coneguts. La cerca binària sempre va a l'element central per comprovar-ho. D'altra banda, la cerca per interpolació pot anar a diferents ubicacions segons el valor de la clau que s'està cercant. Per exemple, si el valor de la clau està més a prop de l'últim element, la cerca d'interpolació és probable que comenci la cerca cap al costat final.
Per trobar la posició a cercar utilitza la fórmula següent.
// La idea de la fórmula és retornar un valor més alt de pos
// quan l'element a cercar està més a prop d'arr[hi]. I
// valor més petit quan està més a prop d'arr[lo]arr[] ==> Matriu on cal cercar els elements
x ==> Element a cercar
lo ==> Índex inicial a arr[]
hola ==> Índex final a arr[]
després de = el +
Hi ha molts mètodes d'interpolació diferents i un d'ells es coneix com a interpolació lineal. La interpolació lineal pren dos punts de dades que assumim com a (x1y1) i (x2y2) i la fórmula és: al punt(xy).
Aquest algorisme funciona de la manera que cerquem una paraula en un diccionari. L'algoritme de cerca per interpolació millora l'algoritme de cerca binària. La fórmula per trobar un valor és: K = > K és una constant que s'utilitza per reduir l'espai de cerca. En el cas de la cerca binària, el valor d'aquesta constant és: K=(baix+alt)/2.
La fórmula per a pos es pot derivar de la següent manera.
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])Algorisme
La resta de l'algorisme d'interpolació és el mateix, excepte la lògica de partició anterior.
- Pas 1: En un bucle, calculeu el valor de 'pos' mitjançant la fórmula de posició de la sonda.
- Pas 2: Si és una coincidència, retorneu l'índex de l'element i sortiu.
- Pas 3: Si l'element és inferior a arr[pos] calculeu la posició de la sonda de la submatriu esquerra. En cas contrari, calculeu el mateix a la submatriu dreta.
- Pas 4: Repetiu fins que es trobi una coincidència o la submatriu es redueixi a zero.
A continuació es mostra la implementació de l'algorisme.
// 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 ?>
Sortida
Element found at index 4
Complexitat temporal: O (log 2 (log 2 n)) per al cas mitjà i O(n) per al pitjor cas
Complexitat de l'espai auxiliar: O(1)
Un altre enfocament: -
Aquest és l'enfocament d'iteració per a la cerca per interpolació.
- Pas 1: En un bucle, calculeu el valor de 'pos' mitjançant la fórmula de posició de la sonda.
- Pas 2: Si és una coincidència, retorneu l'índex de l'element i sortiu.
- Pas 3: Si l'element és inferior a arr[pos] calculeu la posició de la sonda de la submatriu esquerra. En cas contrari, calculeu el mateix a la submatriu dreta.
- Pas 4: Repetiu fins que es trobi una coincidència o la submatriu es redueixi a zero.
A continuació es mostra la implementació de l'algorisme.
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' ); }
Sortida
Element found at index 4
Complexitat temporal: O(log2(log2n)) per al cas mitjà i O(n) per al pitjor
Complexitat de l'espai auxiliar: O(1)
