Dado um array classificado de n valores uniformemente distribuídos arr[] escreva uma função para procurar um elemento x específico no array.
A Pesquisa Linear encontra o elemento em tempo O(n) Pesquisa de salto leva O(n) tempo e Pesquisa binária leva tempo O (log n).
A Pesquisa de Interpolação é uma melhoria em relação Pesquisa binária para casos em que os valores em uma matriz classificada são distribuídos uniformemente. A interpolação constrói novos pontos de dados dentro do intervalo de um conjunto discreto de pontos de dados conhecidos. A Pesquisa Binária sempre vai para o elemento do meio para verificar. Por outro lado, a pesquisa por interpolação pode ir para locais diferentes de acordo com o valor da chave que está sendo pesquisada. Por exemplo, se o valor da chave estiver mais próximo do último elemento, a pesquisa de interpolação provavelmente iniciará a pesquisa no lado final.
Para encontrar a posição a ser pesquisada utiliza-se a seguinte fórmula.
// A ideia da fórmula é retornar um valor maior de pos
// quando o elemento a ser pesquisado está mais próximo de arr[hi]. E
// valor menor quando mais próximo de arr[lo]
arr[] ==> Array onde os elementos precisam ser pesquisados
x ==> Elemento a ser pesquisado
lo ==> Índice inicial em arr[]
oi ==> Índice final em arr[]
depois = o +
Existem muitos métodos de interpolação diferentes e um deles é conhecido como interpolação linear. A interpolação linear utiliza dois pontos de dados que assumimos como (x1y1) e (x2y2) e a fórmula é: no ponto (xy).
pandas iterrows
Este algoritmo funciona de forma que procuramos uma palavra em um dicionário. O algoritmo de busca por interpolação melhora o algoritmo de busca binária. A fórmula para encontrar um valor é: K =>K é uma constante usada para restringir o espaço de busca. No caso de busca binária o valor desta constante é: K=(baixo+alto)/2.
A fórmula para pos pode ser derivada da seguinte forma.
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])
Algoritmo
O resto do algoritmo de interpolação é o mesmo, exceto pela lógica de partição acima.
- Etapa 1: Num loop, calcule o valor de 'pos' usando a fórmula de posição da sonda.
- Etapa 2: Se for uma correspondência, retorne o índice do item e saia.
- Etapa 3: Se o item for menor que arr[pos] calcule a posição da sonda da submatriz esquerda. Caso contrário, calcule o mesmo na submatriz direita.
- Etapa 4: Repita até que uma correspondência seja encontrada ou a submatriz seja reduzida a zero.
Abaixo está a implementação do algoritmo.
// 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 ?> Saída
Element found at index 4
Complexidade de tempo: O(log2(registro2n)) para o caso médio e O(n) para o pior caso
Complexidade do Espaço Auxiliar: O(1)
Outra abordagem: -
Esta é a abordagem de iteração para a pesquisa de interpolação.
- Etapa 1: Num loop, calcule o valor de 'pos' usando a fórmula de posição da sonda.
- Etapa 2: Se for uma correspondência, retorne o índice do item e saia.
- Etapa 3: Se o item for menor que arr[pos] calcule a posição da sonda da submatriz esquerda. Caso contrário, calcule o mesmo na submatriz direita.
- Etapa 4: Repita até que uma correspondência seja encontrada ou a submatriz seja reduzida a zero.
Abaixo está a implementação do algoritmo.
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'); }
Saída
Element found at index 4
Complexidade de tempo: O(log2(log2 n)) para o caso médio e O(n) para o pior caso
Complexidade do Espaço Auxiliar: O(1)