Question

How to implement interpolation search in JavaScript

Answer 1

function interpolation_search(arr, item) {
    let low = 0;
    let high = arr.length - 1;
    let mid = -1;
    let index = -1;
    
    while (low <= high) {
        mid = low + ((Math.trunc((high - low) / (arr[high] - arr[low]))) * (item - arr[low]));
        if (arr[mid] == item) {
            index = mid;
            break;
        }
        else {
            if (arr[mid] < item) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
    }
    return index;
}

const arr = [2, 5, 6, 8, 9, 12, 20, 34, 36, 40, 46, 51, 55, 61, 72, 86, 97];
const item = 51;
        
const index = interpolation_search(arr, item);
if (index != -1) {
    console.log("index = " + index);
}
else {
    console.log("Not found");
}




/*
run:

"index = 11"

*/

 

70+ SQL courses for beginners and professionals