Class TernarySearch

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

Inheritance

System.Object

TernarySearch

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 TernarySearch

Methods

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

Implements ternary search recursively on a list of any comparable type. This search is inspired by binary search (hence the naming, 3 versus 2). The difference being that rather than dividing the list into 2 sections, divides it into 3 equal sections and performs the search inside each one of those separately. Notice that only works if the given list is sorted.

Declaration

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

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.
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