Show / Hide Table of Contents

Class ExponentialSearch

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

Inheritance
System.Object
ExponentialSearch
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 ExponentialSearch

Methods

| Improve this Doc View Source

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

Implements exponential search, where the search step is a multiple of 2, hence the naming. Notice that only works if the given list is sorted.

Declaration
[Algorithm(AlgorithmType.Search, "ExponentialSearch", Assumptions = "List is sorted with an ascending order.")]
[SpaceComplexity("O(1)", false, InPlace = true)]
[TimeComplexity(Case.Best, "O(1)")]
[TimeComplexity(Case.Worst, "O(log(i)), i is the index of the key in the list.")]
[TimeComplexity(Case.Average, "O(log(i)), i is the index of the key in the list.")]
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.

  • Improve this Doc
  • View Source
Back to top Generated by DocFX