PHP - Fibonacci Search

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";