Question

How to implement interpolation search in TypeScript

Answer 1

function interpolation_search(arr: number[], item: number) {
    let low: number = 0;
    let high: number = arr.length - 1;
    let mid: number = -1;
    let index: number = -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: number[] = [2, 5, 6, 8, 9, 12, 20, 34, 36, 40, 46, 50, 51, 55, 61, 72, 86, 97];
const item: number = 51;
        
const index: number = interpolation_search(arr, item);
if (index != -1) {
    console.log("index = " + index);
}
else {
    console.log("Not found");
}




/*
run:

"index = 12"

*/

 

70+ SQL courses for beginners and professionals