【查找算法】二分查找/插值查找/斐波那契查找(PHP)

除了排序，查找指定值也是常见的功能，所以非常有必要掌握一下相关算法。经典查找算法有顺序查找、二分查找、差值查找、斐波那契查找。顺序查找比较简单就不介绍了，下面主要介绍剩余三种查询算法的实现原理，PHP代码示例，以及性能分析。
<输入的最好方式就是输出>，本着学习的态度表达一下自己浅显的理解。

1.二分查找
二分查找算法的实现前提是待排数组必须是有序的（以下算法均以升序为例），其主要思想是通过将每次取数组中间位置作为比较对象，小于该位置则到左区间寻找，大于该位置则到右区间寻找，左右区间按照同样的方式，循环取当前区间中间值比较，直到找到最终结果。

代码如下：

function binarySearch(array $arr, int $val)
{
    $len = count($arr);
    $left = 0;//初始区间左下标
    $right = $len - 1;//初始区间右下标
    $result = -1;
    //越界处理
    if ($val > $arr[$right] || $val < $arr[$left]){
        return $result;
    }
    //边界处理
    if ($arr[$left] == $val){
        return $left;
    }elseif ($arr[$right] == $val){
        return $right;
    }else{
        //开始二分查找
        while ($left <= $right) {
            $mid = $left + intval(($right - $left) / 2);//取中间值
            if ($arr[$mid] == $val) {
                return $mid;//返回待查值下标位置
            } elseif ($arr[$mid] > $val) {
                //值在左边
                $right = $mid - 1;
            } else {
                //值在右边
                $left = $mid + 1;
            }
        }
    }
    return $result;//未找到
}

记忆关键词：区间二分
性能分析：时间复杂度O(logn)

2.插值查找
插值查找是二分查找的优化，区别在于：二分查找每次与中间位置进行比较，而插值查找每次与最靠近待查值的位置进行比较，比盲目的二分策略性更强。

代码如下:

function interpolationSearch(array $arr, int $val)
{
    $len = count($arr);
    $left = 0;
    $right = $len - 1;
    $result = -1;
    //边界处理
    if ($val < $arr[$left] || $val > $arr[$right]) {
        return $result;
    }
    while ($left < $right) {
        $mid = $left + abs(($val - $arr[$left]) * ($right - $left) / ($arr[$right] - $arr[$left]));//注意绝对值
        $mid = intval($mid);
        if ($arr[$mid] == $val) {
            return $mid;//返回元素下标
        } elseif ($arr[$mid] > $val) {
            //左侧
            $right = $mid - 1;
        } else {
            //右侧
            $left = $mid + 1;
        }
    }
    return -1;//未找到
}

插值查询的关键在于mid的确定，根据下图等式可得到mid的值

1-mid公式

记忆关键词： 差值比例
性能分析：时间复杂度O(logn)

3.斐波那契查找
斐波那契查找算法是斐波那契数列的应用，斐波那契数列又称黄金分割数列，其核心公式为F(n)=F(n-1)+F(n-2)，即从第三项开始，每一项可以分割为前一项和前两项之和，而前一项与当前项的比值接近0.618，该比例称为黄金分割比例，斐波那契查找算法的核心思想就是将数组按照黄金分割比例进行查找划分。代码实现思路：

• 构造斐波那契数列
• 找到大于等于数组长度的最小值k，即F(k)>=len
• 最大值填充数组多余长度
• 按照黄金分割比例进行查找
• 若未找到，根据差值进入左右分区，左分区长度为F(k-1)，右分区为F(k-2)
• 在新的分区重复黄金分割比例查找，直到找到结果或未找到结果。

代码如下：

/**
 * 获取斐波那契数列值
 * F(1)=F(2)=1,F(k)=F(k-1)+F(k-2),k>=3
 * @param int $k
 * @return int|void
 * @throws Exception
 */
function fioNum(int $k = FIBONACCI_NUM)
{
    if ($k < 1) {
        throw new Exception('k必须为大于0的整数');
    }
    if ($k == 1 || $k == 2) {
        return 1;//数列初始值
    }
    return fioNum($k - 1) + fioNum($k - 2);
}
/**
 * 斐波那契查找
 * @param array $arr
 * @param int $val
 * @return bool|int|mixed
 * @throws Exception
 */
function fibSearch(array $arr, int $val)
{
    $len = count($arr);
    //数组长度小于3，直接用顺序查找
    if ($len < 3) {
        foreach ($arr as $k => $v) {
            if ($v == $val) {
                return $k;
            }
        }
        return -1;
    }
    $left = 0;
    $right = $len - 1;
    $fibArr = [];//斐波那契数列
    $k = 0;//斐波那契数列最小值初始化
    try {
        //1.构造斐波那契数列
        $fibNum = 0;
        while ($len > $fibNum) {
            //2.寻找大于等于数组长度的最小值k
            $k++;
            $fibNum = fioNum($k);
            $fibArr[] = $fibNum;
        }
    } catch (Exception $e) {
        throw new Exception($e->getMessage());
    }
    //3.对多余部分进行最大值填充
    for ($i = $len - 1; $i < $fibNum; $i++) {
        $arr[$i] = $arr[$right];
    }
    $k--;//数组下标从0开始，所以要减1
    //4.进行黄金分割查找
    while ($left <= $right) {
        $mid = $left + $fibArr[$k - 1] - 1;//确定黄金分割位置，长度-1表示间隔距离
        if ($arr[$mid] == $val) {
            //判断是否是填充数据
            if ($mid > $right) {
                return $right;
            } else {
                return $mid;
            }
        } elseif ($arr[$mid] > $val) {
            //在左边
            $right = $mid - 1;
            $k -= 1;//左边区域长度F(k-1)
        } else {
            //在右边
            $left = $mid + 1;
            $k -= 2;//右边区域长度F(k-2)
        }
    }
    return -1;//没找到
}

记忆关键词： 斐波那契数列、黄金分割比例
性能分析：时间复杂度O(logn)