Question

How to implement interpolation search in PHP

Answer 1

function interpolation_search($arr, $item) {
    $low = 0;
    $high = count($arr) - 1;
    $mid = -1;
    $index = -1;
    
    while ($low <= $high) {
        $mid = $low + (((int)(($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;
}

$arr = array(2, 5, 6, 8, 9, 12, 20, 34, 36, 40, 46, 51, 55, 61, 72, 86, 97);
$item = 51;

$index = interpolation_search($arr, $item);
if ($index != -1) {
    echo "index = " . strval($index);
}
else {
    echo "Not found";
}




/*
run:

index = 11

*/

 

70+ SQL courses for beginners and professionals