给定一个由n个均匀分布的值arr[]组成的排序数组，编写一个函数来搜索数组中的特定元素x。 线性搜索在O（n）时间内找到元素， 跳转搜索 需要(√ n） 时间和 二进制搜索 花点时间。 插值搜索是对传统搜索的改进 二进制搜索 例如，排序数组中的值均匀分布。二进制搜索总是转到中间元素进行检查。另一方面，插值搜索可以根据正在搜索的键的值去到不同的位置。例如，如果关键点的值更接近最后一个元素，则插值搜索可能会朝着端点开始搜索。 为了找到要搜索的位置，它使用以下公式。
null
// The idea of formula is to return higher value of pos// when element to be searched is closer to arr[hi]. And// smaller value when closer to arr[lo]pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]arr[] ==> Array where elements need to be searchedx ==> Element to be searchedlo ==> Starting index in arr[]hi ==> Ending index in arr[]
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 lo,hi and x in the equationarr[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 = pospos = lo + (x - arr[lo]) *(hi - lo)/(arr[hi] - arr[lo])
算法 除上述分区逻辑外，其余插值算法相同。 第一步： 在循环中，使用探针位置公式计算“pos”的值。 第二步： 如果是匹配项，则返回该项的索引，然后退出。 第三步： 如果项目小于arr[pos]，则计算左侧子阵列的探头位置。否则，在右边的子数组中计算相同的值。 第四步： 重复此操作，直到找到匹配项或子数组减少到零。 下面是算法的实现。
C++
// C++ program to implement interpolation search #include<bits/stdc++.h> 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 n, int x) { // Find indexes of two corners int lo = 0, hi = (n - 1); // Since array is sorted, an element present // in array must be in range defined by corner while (lo <= hi && x >= arr[lo] && x <= arr[hi]) { if (lo == hi) { if (arr[lo] == x) return lo; return -1; } // Probing the position with keeping // uniform distribution in mind. int 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 upper part if (arr[pos] < x) lo = pos + 1; // If x is smaller, x is in the lower part else hi = pos - 1; } 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, n, 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 Mukul Singh. |
C++
// C++ program to implement interpolation // search with recursion #include <bits/stdc++.h> 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 <stdio.h> // 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 |
Python3
# 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> |
输出
Element found at index 4
本文由 阿尤·萨赫德夫 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
