<?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);

插入查找

  • 由