interpolation search
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 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])
Source: www.geeksforgeeks.org
interpolation search
#include<bits/stdc++.h> using namespace std; int interpolationSearch(vector < int > A, int data) { int low = 0, high = A.size() - 1, mid; while (low <= high) { mid = low + (((data - A[low]) * (high - low)) / (A[high] - A[low])); if (data == A[mid]) return mid; if (data > A[mid]) low = mid + 1; else high = mid - 1; } return -1; } int main() { int n, data; cin >> n; vector < int > a(n); for (int i = 0; i < n; i++) cin >> a[i]; cin >> data; cout << interpolationSearch(a, data); }
Source: www.topcoder.com