# 費氏搜尋

December 11, 2021

## 解法思路

-∞ 1 3 5 7 9 13 15 17 19 20

1. 找到不大於 n + 1 的最大 Fʸ
2. 求 x = y - 1
3. 求 m = n - Fʸ

``````F₀ = 0
F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂
``````

## 程式實作

``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define INT_MIN -9999

void createFibonacci(int[], int);     // 建立費氏數列
int findY(int[], int);          // 找Y值
int fibonacciSearch(int[], int, int);  // 費氏搜尋

int main(void) {
int number[] = {1, 2, 3, 5, 6, 8, 9, 10, 11};
int length = sizeof(number) / sizeof(int);

printf("數列：");
int i;
for(i = 0; i < length; i++)
printf("%d ", number[i]);

printf("\n輸入尋找對象：");
int find;
scanf("%d", &find);

if((i = fibonacciSearch(number, length, find)) >= 0)
printf("找到數字於索引 %d ", i);
else
printf("\n找不到指定數");

printf("\n");

return 0;
}

// 建立費氏數列
void createFibonacci(int Fib[], int length) {
Fib[0] = 0;
Fib[1] = 1;
int i;
for(i = 2; i < length; i++)
Fib[i] = Fib[i-1] + Fib[i-2];
}

// 找 y 值
int findY(int Fib[], int n) {
int i = 0;
while(Fib[i] <= n) i++;
i--;
return i;
}

// 費氏搜尋
int fibonacciSearch(int number[], int length, int find) {
int* Fib = malloc(length * sizeof(int));
int f;
for(f = 0; f < length; f++) {
Fib[f] = INT_MIN;
}

createFibonacci(Fib, length);

int y  = findY(Fib, length + 1);
int m = length - Fib[y];
int x = y - 1;

int i = x;
if(number[i] < find)
i += m;

int result = -1;
while(Fib[x] > 0) {
if(number[i] < find)
i += Fib[--x];
else if(number[i] > find)
i -= Fib[--x];
else {
result = i;
break;
}
}

free(Fib);

return result;
}
``````
``````public class Search {
public static int fibonacci(int[] number, int des) {
int[] fib = createFibonacci(number.length);
int max = number.length - 1;
int y  = findY(fib, max+1);
int m = max - fib[y];
int x = y - 1;

int i = x;

if(number[i] < des)
i += m;

while(fib[x] > 0) {
if(number[i] < des)
i += fib[--x];
else if(number[i] > des)
i -= fib[--x];
else
return i;
}

return -1;

}

private static int[] createFibonacci(int max) {
int[] fib = new int[max];
for(int i = 0; i < fib.length; i++) {
fib[i] = Integer.MIN_VALUE;
}

fib[0] = 0;
fib[1] = 1;

for(int i = 2; i < max; i++)
fib[i] = fib[i-1] + fib[i-2];

return fib;
}

private static int findY(int[] fib, int n) {
int i = 0;
while(fib[i] <= n) i++;
i--;
return i;
}

public static void main(String[] args) {
int[] number = {1, 2, 3, 5, 6, 8, 9, 10, 11};
int find = Search.fibonacci(number, 2);
System.out.println(find >= 0 ? "找到數值於索引" + find : "找不到數值");
}
}
``````
``````import sys
def search(number, des):
fib = fibonacci(len(number))
max = len(number) - 1
y = findY(fib, max + 1)
m = max - fib[y]
x = y - 1

i = x
if number[i] < des:
i += m
while fib[x] > 0:
if number[i] < des:
x -= 1
i += fib[x]
elif number[i] > des:
x -= 1
i -= fib[x]
else:
return i
return -1

def fibonacci(max):
fib = [sys.maxsize] * max
fib[0] = 0
fib[1] = 1
for i in range(2, max):
fib[i] = fib[i -1] + fib[i - 2]
return fib

def findY(fib, n):
i = 0
while fib[i] <= n:
i += 1
return i - 1

number = [1, 4, 2, 6, 7, 3, 9, 8]
number.sort()
find = search(number, 3)
print("找到數值於索引 " + str(find) if find >= 0 else "找不到數值")
``````
``````object Search {
def fibonacci(number: Array[Int], des: Int): Int = {
val fib = fibonacci(number.length)

def y(i: Int): Int = if(fib(i) <= number.length) y(i + 1) else i - 1
def search(x: Int, i: Int): Int = {
if(fib(x) > 0 && number(i) != des) {
if(number(i) < des) search(x - 1, i + fib(x - 1))
else search(x - 1, i - fib(x - 1))
} else i
}

val x = y(0) - 1
if(number(x) < des) search(x, x + number.length - 1 - fib(x + 1))
else search(x, x)
}

private def fibonacci(max: Int): Array[Int] = {
def fib(n: Int): Int = n match {
case 0 => 0
case 1 => 1
case _ => fib(n - 1) + fib(n - 2)
}
(for(i <- 0 until max) yield fib(i)).toArray
}
}

val number = Array(1, 2, 3, 4, 6, 7, 8)
val find = Search.fibonacci(number, 3)
println(if(find >= 0) "找到數值於索引 " + find else "找不到數值")
``````
``````# encoding: UTF-8
class Integer
N_BYTES = [42].pack('i').size
N_BITS = N_BYTES * 8
MAX = 2 ** (N_BITS - 2) - 1
MIN = -MAX - 1
end

def search(number, des)
fib = fibonacci(number.length)
max = number.length - 1
y = findY(fib, max + 1)
m = max - fib[y]
x = y - 1
i = x
if number[i] < des
i += m
end
while fib[x] > 0
if number[i] < des
x -= 1
i += fib[x]
elsif number[i] > des
x -= 1
i -= fib[x]
else
return i
end
end
-1
end

def fibonacci(max)
fib = Array.new(max, Integer::MAX)
fib[0] = 0
fib[1] = 1
2.upto(max - 1) { |i|
fib[i] = fib[i -1] + fib[i - 2]
}
fib
end

def findY(fib, n)
i = 0
while fib[i] <= n
i += 1
end
i - 1
end

number = [1, 4, 2, 6, 7, 3, 9, 8]
number.sort!
find = search(number, 2)
print find >= 0 ? "找到數值於索引 " + find.to_s : "找不到數值", "\n"
``````
``````function fibonacciSearch(number, des) {
let fib = createFibonacci(number.length);
let max = number.length - 1;
let y  = findY(fib, max+1);
let m = max - fib[y];
let x = y - 1;

let i = x;

if(number[i] < des) {
i += m;
}

while(fib[x] > 0) {
if(number[i] < des)
i += fib[--x];
else if(number[i] > des)
i -= fib[--x];
else
return i;
}

return -1;

}

function createFibonacci(max) {
let fib = [];
for(let i = 0; i < max; i++) {
fib[i] = Number.MAX_SAFE_INTEGER;
}

fib[0] = 0;
fib[1] = 1;

for(let i = 2; i < max; i++) {
fib[i] = fib[i-1] + fib[i-2];
}

return fib;
}

function findY(fib, n) {
let i = 0;
while(fib[i] <= n) i++;
i--;
return i;
}

let number = [1, 2, 3, 5, 6, 8, 9, 10, 11];
console.log(fibonacciSearch(number, 2));
``````
``````import Data.List

fibseq max =
_fib [1, 0] max 2
where
_fib seq max count =
if max == count then reverse seq
else
let f = (seq !! 0) + (seq !! 1)
in _fib (f:seq) max (count + 1)

findy fib n = (length \$ takeWhile (<=n) fib) - 1

fibSearch number n =
let
leng = length number
fib = fibseq leng
y = findy fib leng
m = leng - 1 - (fib !! y)
x = y - 1
i = if (number !! x) < n then x + m else x
in _search fib i x
where
_search fib i x =
if (fib !! x) <= 0 then -1
else
let elem = number !! i
x_1 = x - 1
in
if elem < n then _search fib (i + (fib !! x_1)) x_1
else if elem > n then _search fib (i - (fib !! x_1)) x_1
else i

main = print \$ fibSearch [1, 2, 3, 4, 6, 7, 8] 6
``````