Kurs:Algorithmen und Datenstrukturen/Vorlesung/Fibonacci Suche

Fibonacci Suche

Dieses Kapitel behandelt die Fibonacci Suche. Die im vorherigen Kapitel behandelte binäre Suche hat Nachteile. Die binäre Suche ist der am häufigsten verwendete Algorithmus zur Suche in sortierten Arrays. Die Sprünge zu verschiedenen Testpositionen sind allerdings immer recht groß. Dies kann nachteilig sein, wenn das Array nicht vollständig im Speicher vorliegt (oder bei Datenträgertypen wie Kassetten). Außerdem werden neue Positionen durch Division berechnet und je nach Prozessor ist dies eine aufwändigere Operation als Addition und Subtraktion. Daher nehmen wir die Fibonacci Suche als eine weitere Alternative.

Fibonacci Zahlen

Zur Erinnerung, die Folge der Fibonacci Zahlen $F_n$ für $n\ge 0$ ist definiert durch

$F_0=0$
$F_1=1$
$F_2=1$
$F_i=F_{i-1}+F_{i-2}$ für $i>1$

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
$F_i$	0	1	1	2	3	5	8	13	21	34	55	89	144	233	377

Anstatt wie bei der binären Suche das Array in gleich große Teile zu teilen, wird das Array in Teilen entsprechend der Fibonacci-Zahlen geteilt. Es wird zunächst das Element an Indexposition m betrachtet, wobei m die größte Fibonaccizahl ist, die kleiner als die Arraylänge ist. Nun fährt man rekursiv mit dem entsprechenden Teilarray fort.

Rekursive Fibonacci Suche

public int fibonacciSearch(int[] arr, int elem) {
	return fibonacciSearchRec(arr,elem,0,arr.length-1);
}

public int fibonacciSearchRec(int[] arr, int elem, int u, int o) {
	int k = 0;
	while (fib(k) < o-u) k++;
	if (elem == arr[u+fib(--k)])
		return u+fib(k);
	if (u == o)
		return -1;
	if (elem < arr[u+fib(k)])
		return fibonacciSearchRec(arr, elem, u, u+fib(k)-1);
	return fibonacciSearchRec(arr ,elem, u+fib(k)+1, o);
}

Beispiel

9

19

21

34

87

102

158

159

199

205

Wo befindet sich die 133?

1. fibonacciSearchRec(arr,133,0,9)
   1. fib(6)=8 < 9-0 (und maximal)
   2. arr[fib(6)+0] = arr[8] = 199 > 133
2. fibonacciSearchRec(arr,133,0,7)
   1. fib(5)=5 < 7-0 (und maximal)
   2. arr[fib(5)+0] = arr[5] = 102 < 133
3. fibonacciSearchRec(arr,133,6,7)
   1. fib(0)=0 < 7-6 (und maximal)
   2. arr[fib(0)+6] = arr[6] = 158 > 133
4. fibonacciSearchRec(arr,133,6,6)
   1. Suche erfolglos

Wo befindet sich die 87?

1. fibonacciSearchRec(arr,87,0,9)
   1. fib(6)=8 < 9-0 (und maximal)
   2. arr[fib(6)+0] = arr[8] = 199 > 87
2. fibonacciSearchRec(arr,87,0,7)
   1. fib(5)=5 < 7-0 (und maximal)
   2. arr[fib(5)+0] = arr[5] = 102 > 87
3. fibonacciSearchRec(arr,87,0,4)
   1. fib(4)=3 < 4-0 (und maximal)
   2. arr[fib(4)+0] = arr[3] = 34 < 87
4. fibonacciSearchRec(arr,87,4,4)
   1. Suche erfolgreich

Aufwands Analyse

Die Fibonacci Suche hat dieselbe Komplexität wie die binäre Suche. Die Anzahl der Vergleiche im besten Fall ist 1 und die Anzahl der Vergleiche im Durchschnitt (erfolgreich/erfolglos) und im schlechtesten Fall ist $lo{g}_{2}n$. Die nötigen Fibonaccizahlen können vorab berechnet und in einem (statischen) Array gespeichert werden. Für Arrays mit weniger als 100.000.000 Elementen werden “nur” die ersten 50 Fibonaccizahlen benötigt. Als Operationen können nur Subtraktion und Addition genutzt werden und die “Sprünge” zwischen Arrayposition ist im Durchschnitt geringer als bei binärer Suche.