Class LinearSearch

An object able to search in linear time for items in direct random access structures, such as lists and arrays, which are monodimensional and implement the interface.

Inheritance
System.Object
LinearSearch
Implements
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: MoreStructures.Lists.Searching
Assembly: MoreStructures.dll
Syntax
public class LinearSearch : ISearch
Remarks


Unlike BinarySearch, this implementation doesn't make any assumption on the order of items in in the data structure.

Methods

| Improve this Doc View Source

First<T>(IEnumerable<T>, T, Nullable<IComparer<T>>, Nullable<Int32>, Nullable<Int32>)


This specific implementation does not make any assunption on source being sorted.

Declaration
public int First<T>(IEnumerable<T> source, T item, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null)
Parameters
Type Name Description
IEnumerable<T> source
T item
System.Nullable<IComparer<T>> comparer
System.Nullable<System.Int32> fromIndex
System.Nullable<System.Int32> toIndex
Returns
Type Description
System.Int32
Type Parameters
Name Description
T
Remarks

The algorithm linearly scans the search space from fromIndex to toIndex, one index at every iteration, reducing it linearly to a single item or to an empty set.
Time Complexity = O(n), Space Complexity = O(1), where n = number of items between fromIndex and toIndex.

| Improve this Doc View Source

FirstAll<T>(IEnumerable<T>, Nullable<IComparer<T>>, Nullable<Int32>, Nullable<Int32>)


This specific implementation does not make any assunption on source being sorted.

Declaration
public IDictionary<T, int> FirstAll<T>(IEnumerable<T> source, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null)
Parameters
Type Name Description
IEnumerable<T> source
System.Nullable<IComparer<T>> comparer
System.Nullable<System.Int32> fromIndex
System.Nullable<System.Int32> toIndex
Returns
Type Description
IDictionary<T, System.Int32>
Type Parameters
Name Description
T
Remarks

ALGORITHM
The algorithm linearly scans the search space from fromIndex to toIndex, one index at every iteration, collecting first occurrences into a .

COMPLEXITY
Time Complexity = O(n), Space Complexity = O(sigma), where:
- n is the number of items between fromIndex and toIndex.
- For "large alphabets" scenarios (such as when the alphabet is int - 2^32 possible values, but source is way smaller than that), sigma is the number of distinct elements of source.
- For "small alphabets" scenarios (such as when the alphabet is comprised of few symbols only), sigma is the size of the alphabet.
- In either scenario the worst case of the O(sigma) Space Complexity is O(n), which is when all the symbols in source are different from each other).

| Improve this Doc View Source

Interval<T>(IEnumerable<T>, T, Nullable<IComparer<T>>, Nullable<Int32>, Nullable<Int32>)


This specific implementation does not make any assunption on source being sorted.

Declaration
public (int first, int last) Interval<T>(IEnumerable<T> source, T item, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null)
Parameters
Type Name Description
IEnumerable<T> source
T item
System.Nullable<IComparer<T>> comparer
System.Nullable<System.Int32> fromIndex
System.Nullable<System.Int32> toIndex
Returns
Type Description
System.ValueTuple<System.Int32, System.Int32>
Type Parameters
Name Description
T
Remarks

The algorithm linearly scans the search space from fromIndex to toIndex, one index at every iteration.
It just stores the smallest and the biggest index among the ones which correspond to items equal to item. So it has constant, and not linear, space requirements.
Time Complexity = O(n), Space Complexity = O(1), where n = number of items between fromIndex and toIndex.

| Improve this Doc View Source

Last<T>(IEnumerable<T>, T, Nullable<IComparer<T>>, Nullable<Int32>, Nullable<Int32>)


This specific implementation does not make any assunption on source being sorted.

Declaration
public int Last<T>(IEnumerable<T> source, T item, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null)
Parameters
Type Name Description
IEnumerable<T> source
T item
System.Nullable<IComparer<T>> comparer
System.Nullable<System.Int32> fromIndex
System.Nullable<System.Int32> toIndex
Returns
Type Description
System.Int32
Type Parameters
Name Description
T
Remarks

The algorithm linearly scans the search space from toIndex to fromIndex, one index at every iteration, reducing it linearly to a single item or to an empty set.
Time Complexity = O(n), Space Complexity = O(1), where n = number of items between fromIndex and toIndex.

| Improve this Doc View Source

Nth<T>(IEnumerable<T>, T, Int32, Nullable<IComparer<T>>, Nullable<Int32>, Nullable<Int32>)


This specific implementation does not make any assunption on source being sorted.

Declaration
public int Nth<T>(IEnumerable<T> source, T item, int occurrenceRank, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null)
Parameters
Type Name Description
IEnumerable<T> source
T item
System.Int32 occurrenceRank
System.Nullable<IComparer<T>> comparer
System.Nullable<System.Int32> fromIndex
System.Nullable<System.Int32> toIndex
Returns
Type Description
System.Int32
Type Parameters
Name Description
T
Remarks

The algorithm linearly scans the search space from toIndex to fromIndex, one index at every iteration, reducing it linearly to a single item or to an empty set.
It just stores the current counter of occurrences of item in source, not all of them. So it has constant, and not linear, space requirements.
Time Complexity = O(n), Space Complexity = O(1), where n = number of items between fromIndex and toIndex.

Implements

Extension Methods