PHP ordered list search----interpolation search

Preface:

We introduced binary search earlier, but let’s think about it, why must it be folded in half? Rather than folding it into a quarter or more?

For example, when searching for "apple" in an English dictionary, when you open the dictionary, do you subconsciously turn to the front page or the back page? If you check "zoo" again, how will you check it? Obviously you don't start looking up from the middle of the dictionary, but you look forward or backward with a certain purpose.

Similarly, for example, if we want to find 5 in an array with 100 elements evenly distributed from small to large in the value range of 0 ~ 10000, we naturally start the search by considering the smaller array subscript first.

The above analysis is actually the idea of ​​interpolation search, which is an improvement of binary search.

Basic idea:

The search method is based on comparing the keyword key to be searched with the keywords of the largest and smallest records in the lookup table. The core lies in the interpolation calculation formula:
$key - $arr[$low]
——————————-
$arr[$high] - $arr[$low]

Code:

<?php
//插值查找(前提是数组必须是有序数组) 事件复杂度　O(logn)
//但对于数组长度比较大，关键字分布又是比较均匀的来说，插值查找的效率比折半查找的效率高
$i = 0;    //存储对比的次数
//@param 待查找数组
//@param 待搜索的数字
function insertsearch($arr,$num){
    $count = count($arr);
    $lower = 0;
    $high = $count - 1;
    global $i;
    while($lower <= $high){
        $i ++; //计数器
        if($arr[$lower] == $num){
            return $lower;
        }
        if($arr[$high] == $num){
            return $high;
        }
        // 折半查找 ： $middle = intval(($lower + $high) / 2);
        $middle = intval($lower + ($num - $arr[$lower]) / ($arr[$high] - $arr[$lower]) * ($high - $lower)); 
        if($num < $arr[$middle]){
            $high = $middle - 1;
        }else if($num > $arr[$middle]){
            $lower = $middle + 1;
        }else{
            return $middle;
        }
    }
    return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = insertsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

Summary:

From the time complexity point of view, it is also O(logn), but it is longer for ordered tables, and the keyword distribution has a relatively even lookup table Generally speaking, the average performance of the interpolation search algorithm is much better than that of binary search. On the contrary, if the distribution in the array is similar to {0, 1, 2, 2000, 2001,. . . 999998, 999999} This kind of extremely uneven data, using interpolation search may not be a very suitable choice.

The above is the content of PHP ordered table search----interpolation search. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!