问题描述
用 PHP 编写斐波那契查找
要求: 查询失败返回 -1
; 查询成功返回下标
给定: $A = [1, 3, 5, 8, 13, 19, 20, 31, 43, 50];
查询 8
,结果返回: 3
代码实现
该算法详解请看: 《C++ 数据结构 (二) 向量 (6) 斐波那契查找》
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
<?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) . "\n";
else echo fibSearch($A, 8, 0, count($A), $fibArr) . "\n";
本文由
Oscaner
创作, 采用
知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名