Class InterpolationSearch

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

Inheritance

System.Object

InterpolationSearch

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 InterpolationSearch

Methods

| Improve this Doc View Source

GetStartIndex<T>(List<T>, T, Int32, Int32)

Computes an index to start the search from, dependent on the value of key. This formula is such that if the key is closer to the value in the startIndex, the search start point will be chosen closer to the startIndex, and if the key is closer to the value at endIndex, the search start point will be chosen closer to the endIndex.

Declaration

public static int GetStartIndex<T>(List<T> sortedList, T key, int startIndex, int endIndex)
    where T : IComparable<T>

Parameters

Type	Name	Description
System.Collections.Generic.List<T>	sortedList	A sorted list of any comparable type that are also uniformly distributed.
T	key	The value that is being searched for.
System.Int32	startIndex	The lowest (left-most) index of the list - inclusive.
System.Int32	endIndex	The highest (right-most) index of the list - inclusive.

Returns

Type	Description
System.Int32	The index in the list at which to start the search.

Type Parameters

Name	Description
T

| Improve this Doc View Source

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

Searches in a sorted list of any comparable type, where values have a uniform distribution. Interpolation search is an improvement over binary search, and has a very similar implementation, the only main difference is where (which index in the array) the search starts at. The search is named interpolation, as it always has two main poles that it moves back and forth between them, these poles are the start index and the end index of the list. Notice that only works if the given list is sorted.

Declaration

[Algorithm(AlgorithmType.Search, "InterpolationSearch", Assumptions = "List is sorted with an ascending order, and elements are driven from a uniform distribution.")]
[SpaceComplexity("O(1)", false, InPlace = true)]
[TimeComplexity(Case.Best, "O(1)")]
[TimeComplexity(Case.Worst, "O(n)")]
[TimeComplexity(Case.Average, "O(Log(Log(n)))")]
public static int Search<T>(List<T> sortedList, T key, int startIndex, int endIndex)
    where T : IComparable<T>

Parameters

Type	Name	Description
System.Collections.Generic.List<T>	sortedList	A sorted list of any comparable type that are also uniformly distributed.
T	key	The value that is being searched for.
System.Int32	startIndex	The lowest (left-most) index of the list - inclusive.
System.Int32	endIndex	The highest (right-most) index of the list - inclusive.

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