Interpolation Search

searching.js

// ES6 Arrow Function
const interpolationSearch = (arr, k) => {
    let n = arr.length;
    let low = 0, high = n - 1;
  
    while(low <= high && k >= arr[low] && k <= arr[high]) {
        // finding the position 
        let pos = low + 
            Math.floor(((k - arr[low]) * (high - low)) / (arr[high] - arr[low]));
      
        if(arr[pos] < k) {
            low = pos + 1;
        } else if(arr[pos] > k) {
            high = pos - 1;
        } else {
            return pos;
        }
    }
  
    return -1;
}

// let testArray = [1,2,3,4,5,6,7,8,9,10];
// let k = 5;
// interpolationSearch(testArray, k);
// output => 4;