Class FibonacciSearch

Implements Fibonacci search algorithm for finding a specific value in a sorted list.

Inheritance

System.Object

FibonacciSearch

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: AlgorithmsAndDataStructures.Algorithms.Search

Assembly: AlgorithmsAndDataStructures.dll

Syntax

public class FibonacciSearch

Methods

GetSmallestFibonacciBiggerThanNumber(Int32)

Computes the smallest Fibonacci number that is greater than number. Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Declaration

public static FibonacciElement GetSmallestFibonacciBiggerThanNumber(int number)

Parameters

Type	Name	Description
System.Int32	number	The integer we want to compute the closest Fibonacci to it that is bigger than or equal to it.

Returns

Type	Description
FibonacciElement	The Fibonacci number.

Search<T>(List<T>, T)

Implements Fibonacci search.

Declaration

[Algorithm(AlgorithmType.Search, "FibonacciSearch", Assumptions = "List is sorted with an ascending order.")]
[SpaceComplexity("O(1)", false, InPlace = true)]
[TimeComplexity(Case.Best, "O(1)")]
[TimeComplexity(Case.Worst, "O(Log(n))")]
[TimeComplexity(Case.Average, "O(Log(n))")]
public static int Search<T>(List<T> sortedList, T key)
    where T : IComparable<T>

Parameters

Type	Name	Description
System.Collections.Generic.List<T>	sortedList	A sorted list of any comparable type.
T	key	The value that is being searched for.

Returns

Type	Description
System.Int32	The index of the key in the list, and -1 if it does not exist in the list.

Type Parameters

Name	Description
T	Type of the values in the sorted list.