Class BinarySearch

An object able to search in logarithmic time for items in direct random access structures, such as lists and arrays, which are monodimensional, implement the interface and are sorted in ascending order according to the provided comparer (which is the property enabling the search to be carried out in O(log(n)) time.

Inheritance
System.Object
BinarySearch
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 BinarySearch : ISearch
Remarks


The sorting order assumed by this search can be reversed by simply inverting the comparer implementation.

Methods

| Improve this Doc View Source

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


This specific implementation assumes that source is sorted in ascending order.

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 split in half the search space at every iteration, reducing it exponentially to a single item or to an empty set.
Time Complexity = O(log(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 assumes that source is sorted in ascending order.

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


The size of the output and the Space Complexity is O(sigma), where:
A binary search for the next different element gives an overall O(sigma * log(sigma)) Time Complexity.

| Improve this Doc View Source

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


This specific implementation assumes that source is sorted in ascending order.

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 peforms two successive binary search operations: the first to find the lower extreme of the interval and the second to find the higher extreme of the interval. Each binary search runs in logarithmic time.
Time Complexity = O(log(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 assumes that source is sorted in ascending order.

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 split in half the search space at every iteration, reducing it exponentially to a single item or to an empty set.
Time Complexity = O(log(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 assumes that source is sorted in ascending order.

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 first performs a binary search to find the index i of the 1st item. Then it checks whether the n-th occurrence of the item exists at index i + n, taking advantage of the fact that source is sorted. The first step takes logarithmic time, whereas the second step takes constant time and space to execute.
Time Complexity = O(log(n)), Space Complexity = O(1), where n = number of items between fromIndex and toIndex.

Implements

Extension Methods