В каком случае мы можем использовать алгоритм интерполяции поиска вместо алгоритма двоичного поиска?

У меня есть два отсортированных массива:

$idProducts = [2,9,25,666,1001,1002,1005,2546...n]; //almost 55.000 values
$someIds =    [1,9,11,12,99,111,855...n]; //almost 2.500 values

Я пытаюсь сделать новый массив из пересечения idProducts и $ someIds.
Я применил 3 алгоритма поиска: линейный, двоичный, межполярный поиск, но только линейный и двоичный алгоритмы работают правильно:

foreach($someIds as $id){
if(interpolation_search($idProducts, $id) >=0){
$newArray[]=$id;
}
}
function interpolation_search($list, $x)
{
$l = 0;
$r = count($list) - 1;

while ($l <= $r) {
if ($list[$l] == $list[$r]) {
if ($list[$l] == $x) {
return $l;
} else {
// not found
return -1;
}
}

$k = ($x - $list[$l])/($list[$r] - $list[$l]);

// not found
if ($k < 0 || $k > 1) {
return -1;
}

$mid = round($l + $k*($r - $l));

if ($x < $list[$mid]) {
$r = $mid - 1;
} else if ($x > $list[$mid]) {
$l = $mid + 1;
} else {
// success!
return $mid;
}

// not found
return -1;
}

}

В любом случае, лучшим решением было:

$idProducts = array_flip($idProducts);
foreach ($someIds as $id){
if (isset($idProducts [$id])===true){
$newArray[]=$id;
}
}

Но я хочу знать, почему интерполяция не работает должным образом в моем случае, и в этом случае мы можем реализовать поиск алгоритма интерполяции.

Спасибо.