interpolation-search-recursive.ts

function InterpolationSearchRecursive(array: number[], key: number, startIndex: number, lastIndex: number): number {
    const position =
        Math.floor(startIndex + (
            (lastIndex - startIndex) /
            (array[lastIndex] - array[startIndex]) *
            (key - array[startIndex])));
    // 1st condition, to make sure we are not out of bounds of array
    // 2nd and 3rd condition to make sure that the key would be present in indexes [startIndex, lastIndex]
    if (startIndex <= lastIndex && key >= array[startIndex] && key <= array[lastIndex]) {
        if (array[position] === key) {
            return position;
        } else if (key < array[position]) {
            lastIndex = position - 1;
        } else {
            startIndex = position + 1;
        }
        return InterpolationSearchRecursive(array, key, startIndex, lastIndex);
    }
    return -1;
}