<?php
/**
* 插入查找
*
* 与二分查找逻辑一样,只不过查找middle时有区别
* 插入查找适合分布比较均匀的且数量较大的,如果分布不是均匀,则
* 不见得比二分快
*
* User: Vega.Lee
* Date: 2020/6/13
* Time: 20:36
*/
function insertSearch ($arr, $left, $right, $searchValue)
{
//判断当左指针不在大于右指针或者超过数组最大值最小值时,进行返回处理
if (($left > $right) || ($arr[0] > $searchValue || $arr[count($arr) - 1] < $searchValue))
{
return -1;
}
$middle_index = $left + ($right - $left) * intval(($searchValue - $arr[$left]) / ($arr[$right] - $arr[$left]));
if ($arr[$middle_index] < $searchValue)
{
//如果比中间值大则向右移
return insertSearch($arr, $middle_index + 1, $right, $searchValue);
}
elseif ($arr[$middle_index] > $searchValue)
{
//如果比中间值大则向左移
return insertSearch($arr, $left, $middle_index - 1, $searchValue);
}
else
{
return $middle_index;
}
}
$arr = [1,2,3,4,5,6,7,8,9,10,11,12,13];
$search = insertSearch($arr, 0, count($arr) - 1, 5);
var_dump($search);