PHP – Fibonacci Search
     发布在:PHP      浏览:54      评论:0 条评论

问题描述

用 PHP 编写斐波那契查找

要求:查询失败返回 -1;查询成功返回下标

给定:$A = [1, 3, 5, 8, 13, 19, 20, 31, 43, 50];

查询 8,结果返回:3

代码实现

该算法详解请看:《C++ 数据结构(二)向量(6)斐波那契查找》

<?php
function fib($k)
{
    $f = 0; $g = 1;

    while (0 < $k--) {
        $g = $g + $f;
        $f = $g - $f;
    }

    return $f;
}

function fibSearch(array $A, int $e, int $lo, int $hi, array $fibArr)
{
    $k = $hi - $lo;

    while ($lo < $hi) {

        while ($hi - $lo < $fibArr[$k--]); // $fibArr[$k] < $hi - $lo < $fibArr[$k + 1]

        $mi = $lo + $fibArr[$k] - 1;

        if ($e < $A[$mi]) $hi = $mi;          // 左区间 [$lo, $mi)

        else if ($A[$mi] < $e) $lo = $mi + 1; // 右区间 ($mi, $lo)

        else return $mi;                      // 匹配

    }

    return -1;
}

$A = [1, 3, 5, 8, 13, 19, 20, 31, 43, 50];

$fibArr = array();

for ($i = 0; $i <= count($A); $i++) $fibArr[$i] = fib($i);

if ($argc > 1) echo fibSearch($A, $argv[1], 0, count($A), $fibArr);

else echo fibSearch($A, 8, 0, count($A), $fibArr);

PHP - Fibonacci Search

Responses