Class Loesung55

java.lang.Object
  Loesung55

 class Loesung55
extends Object

Loesungsvorschlag fuer Aufgabe 5-5: Fibonaccisuche.

Version:

$Revision: 1.2 $

Author:

Arne Johannessen

See Also:

Aufgabenblatt 5

Field Summary

(package private) static int[]

FIBONACCI Die Fibonaccifolge F, angepasst fuer die Fibonaccisuche.

Constructor Summary

Loesung55()

Method Summary

(package private) int	find(int[] array, int key) Durchsucht einen Array mit der Fibonaccisuche.
(package private) int	find(int[] array, int key, int leftIndex, int rightIndex, int fibonacciIndex) Durchsucht einen Array mit der Fibonaccisuche.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

FIBONACCI

static final int[] FIBONACCI

Die Fibonaccifolge F, angepasst fuer die Fibonaccisuche. Diese Folge enthaelt alle Fibonaccizahlen in int; dies sind alle Fibonaccizahlen kleiner oder gleich F₄₆ = 1836311903.

Im Allgemeinen ist die Fibonaccifolge wie folgt definiert:
FIBONACCI[n] = (n == 0 ? 0 : (n == 1 ? 1 : (FIBONACCI[n - 2] + FIBONACCI[n - 1])))

Um klaren Code in der Rekursion zu haben, wird abweichend davon FIBONACCI[0] = 1 definiert; dies spart eine eigene if-Bedingung fuer sehr kurze Teil-Arrays ein. Auch wird FIBONACCI[47] = Integer.MAX_VALUE definiert, um die Korrektheit des Algorithmus auch bei langen Arrays herzustellen.

Constructor Detail

Loesung55

Loesung55()

Method Detail

find

int find(int[] array,
         int key)

Durchsucht einen Array mit der Fibonaccisuche. Zurueckgeliefert wird der Index einer Fundstelle.

Fuer eine Fibonaccisuche muss der Array sortiert sein.

Parameters:

array - das zu durchsuchende Array

key - den zu suchenden Wert

Returns:

den Index desjenigen Elements in array, das den Wert key hat

Throws:

KeyNotFoundException - falls der Array den gesuchten Wert nicht enthaelt

NullPointerException - falls array == null

See Also:

Arrays.sort(int[])

find

int find(int[] array,
         int key,
         int leftIndex,
         int rightIndex,
         int fibonacciIndex)

Durchsucht einen Array mit der Fibonaccisuche. Zurueckgeliefert wird der Index einer Fundstelle.

Fuer eine Fibonaccisuche muss der Array sortiert sein.

Damit diese Methode korrekt ist, muessen beim Aufruf folgende Vorbedingungen erfuellt sein:

• array enthaelt den Suchraum, mit array.length > 0
• array.length > leftIndex >= 0
• rightIndex - leftIndex + 1 == FIBONACCI[fibonacciIndex]
• FIBONACCI enthaelt die Fibonaccifolge, mit FIBONACCI[0] == 1

Das Verhalten dieser Methode bei Nichterfuellung dieser Vorbedingungen ist nicht definiert.

Parameters:

array - das zu durchsuchende Array

key - den zu suchenden Wert

leftIndex - der Index, der die untere Grenze des zu durchsuchenden Bereichs im Array darstellt (einschliesslich)

rightIndex - der Index, der die obere Grenze des zu durchsuchenden Bereichs im Array darstellt (einschliesslich); der Abstand zu leftIndex muss in jedem Fall eine Fibonaccizahl sein

fibonacciIndex - der Index derjenigen Fibonaccizahl, die dem Abstand zwischen leftIndex und rightIndex entspricht

Returns:

den Index desjenigen Elements in array, das den Wert key hat

Throws:

KeyNotFoundException - falls der Array den gesuchten Wert nicht enthaelt

ArrayIndexOutOfBoundsException - falls array.length == 0

NullPointerException - falls array == null

See Also:

Arrays.sort(int[])