Detailed explanation of the steps of PHP ordered list search interpolation search algorithm

This time I will bring you a detailed explanation of the steps of the PHP ordered table search interpolation search algorithm. What are the precautions of the PHP ordered table search interpolation search algorithm. The following is a practical case, let's take a look.

Foreword:

We introduced binary search earlier, but let’s think about it, why must we fold it 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 in the value range from 0 to 10000 evenly distributed from small to large, we naturally first consider the array subscript to be smaller. Start looking small.

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

Basic idea:

Search method based on comparing the keyword key to be found with the keywords of the largest and smallest records in the lookup table , the core of which lies in the interpolation calculation formula. Let’s first look at the calculation formula of half search:

The interpolation search is to improve 1/2 of it and change it to the following Calculation scheme:

The core of the interpolation search algorithm lies in the calculation formula of interpolation:

$num - $arr[$lower]
——————————————
$arr[$high] - $arr[$lower]

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 a time complexity perspective, it is also O(logn) , but for lookup tables with relatively long ordered lists and relatively even distribution of keywords, 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.

I made a special example myself:

$arr = array(0,1,2,2000,2001,2002,2003,2004,5555,69666,99999,100000);
echo "位置：".binsearch($arr,5555);
echo "<br>";
echo "比较次数：".$i;
$i = 0; //重置比较次数
echo "<br>";
echo "位置：".insertsearch($arr,5555);
echo "<br>";
echo "比较次数：".$i;

Result output:

位置：8
比较次数：2
位置：8
比较次数：9

It can be seen that for extremely uneven data, the interpolation search efficiency is lower than the half search.

PS: The binsearch()function mentioned aboveYou can refer to the previous article PHP ordered table search - binary search (halved)

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!

Recommended reading:

PHP long connection use case analysis

How to implement php data export

The above is the detailed content of Detailed explanation of the steps of PHP ordered list search interpolation search algorithm. For more information, please follow other related articles on the PHP Chinese website!