< Summary

Information
Class: MoreStructures.Lists.Searching.BinarySearch
Assembly: MoreStructures
File(s): /home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Searching/BinarySearch.cs
Line coverage
100%
Covered lines: 64
Uncovered lines: 0
Coverable lines: 64
Total lines: 190
Line coverage: 100%
Branch coverage
100%
Covered branches: 34
Total branches: 34
Branch coverage: 100%
Method coverage

Feature is only available for sponsors

Upgrade to PRO version

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
Search(...)100%12100%
First(...)100%1100%
FirstAll(...)100%12100%
Last(...)100%1100%
Interval(...)100%2100%
Nth(...)100%8100%

File(s)

/home/runner/work/MoreStructures/MoreStructures/MoreStructures/Lists/Searching/BinarySearch.cs

#LineLine coverage
 1using MoreStructures.Utilities;
 2
 3namespace MoreStructures.Lists.Searching;
 4
 5/// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 6///
 7/// <summary>
 8/// An object able to search in logarithmic time for items in direct random access structures, such as lists and
 9/// arrays, which are monodimensional, implement the <see cref="IEnumerable{T}"/> interface and are sorted in ascending
 10/// order according to the provided comparer (which is the property enabling the search to be carried out in O(log(n))
 11/// time.
 12/// </summary>
 13/// <remarks>
 14///     <inheritdoc cref="ISearch"/>
 15///     <br/>
 16///     The sorting order assumed by this search can be reversed by simply inverting the comparer implementation.
 17/// </remarks>
 18public class BinarySearch : ISearch
 19{
 20    private static int Search<T>(
 21        IEnumerable<T> source, T item, IComparer<T>? comparer, int? fromIndex, int? toIndex, bool first)
 133422    {
 133423        int length = SearchHelperMethods.ValidateIndexesAndGetLength(source, fromIndex, toIndex);
 24
 132525        comparer ??= Comparer<T>.Default;
 26
 132527        var start = fromIndex ?? 0;
 132528        var end = toIndex ?? length - 1;
 132529        var result = -1;
 614530        while (start <= end)
 482031        {
 482032            var middle = (start, end).Middle();
 482033            var comparison = comparer.Compare(source.ElementAtO1(middle), item);
 482034            if (comparison < 0)
 105035            {
 105036                start = middle + 1;
 105037            }
 377038            else if (comparison == 0)
 178639            {
 178640                result = middle;
 41
 178642                if (first)
 66343                    end = middle - 1;
 44                else
 112345                    start = middle + 1;
 178646            }
 47            else
 198448            {
 198449                end = middle - 1;
 198450            }
 482051        }
 52
 132553        return result;
 132554    }
 55
 56    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 57    /// <summary>
 58    ///     <inheritdoc/>
 59    ///     <br/>
 60    ///     This specific implementation assumes that <paramref name="source"/> is sorted in ascending order.
 61    /// </summary>
 62    /// <remarks>
 63    /// The algorithm split in half the search space at every iteration, reducing it exponentially to a single item
 64    /// or to an empty set.
 65    /// <br/>
 66    /// Time Complexity = O(log(n)), Space Complexity = O(1), where n = number of items between
 67    /// <paramref name="fromIndex"/> and <paramref name="toIndex"/>.
 68    /// </remarks>
 69    public int First<T>(
 70        IEnumerable<T> source, T item, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null) =>
 50071        Search(source, item, comparer, fromIndex, toIndex, true);
 72
 73    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 74    /// <summary>
 75    ///     <inheritdoc/>
 76    ///     <br/>
 77    ///     This specific implementation assumes that <paramref name="source"/> is sorted in ascending order.
 78    /// </summary>
 79    /// <remarks>
 80    ///     <inheritdoc/>
 81    ///     <br/>
 82    ///     The size of the output and the Space Complexity is O(sigma), where:
 83    ///     <inheritdoc cref="LinearSearch.FirstAll{T}(IEnumerable{T}, IComparer{T}?, int?, int?)"
 84    ///         path="/remarks/para[@id='params']"/>
 85    ///     <br/>
 86    ///     A binary search for the next different element gives an overall O(sigma * log(sigma)) Time Complexity.
 87    /// </remarks>
 88    public IDictionary<T, int> FirstAll<T>(
 89        IEnumerable<T> source, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null)
 90        where T : notnull
 6791    {
 6792        var length = SearchHelperMethods.ValidateIndexesAndGetLength(source, fromIndex, toIndex);
 93
 6394        comparer ??= Comparer<T>.Default;
 95
 6396        var start = fromIndex ?? 0;
 6397        var end = toIndex ?? length;
 98
 6399        var result = new Dictionary<T, int> { };
 100
 63101        int currentIndex = start;
 714102        while (currentIndex >= 0 && currentIndex < end && currentIndex < length)
 651103        {
 651104            var currentItem = source.ElementAtO1(currentIndex);
 651105            if (!result.TryGetValue(currentItem, out var _))
 651106                result.Add(currentItem, currentIndex);
 107
 651108            currentIndex = Last(source, currentItem, comparer, currentIndex, toIndex) + 1;
 651109        }
 110
 63111        return result;
 63112    }
 113
 114    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 115    /// <summary>
 116    ///     <inheritdoc/>
 117    ///     <br/>
 118    ///     This specific implementation assumes that <paramref name="source"/> is sorted in ascending order.
 119    /// </summary>
 120    /// <remarks>
 121    /// The algorithm split in half the search space at every iteration, reducing it exponentially to a single item
 122    /// or to an empty set.
 123    /// <br/>
 124    /// Time Complexity = O(log(n)), Space Complexity = O(1), where n = number of items between
 125    /// <paramref name="fromIndex"/> and <paramref name="toIndex"/>.
 126    /// </remarks>
 127    public int Last<T>(
 128        IEnumerable<T> source, T item, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null) =>
 834129        Search(source, item, comparer, fromIndex, toIndex, false);
 130
 131    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 132    /// <summary>
 133    ///     <inheritdoc/>
 134    ///     <br/>
 135    ///     This specific implementation assumes that <paramref name="source"/> is sorted in ascending order.
 136    /// </summary>
 137    /// <remarks>
 138    /// The algorithm peforms two successive binary search operations: the first to find the lower extreme of the
 139    /// interval and the second to find the higher extreme of the interval. Each binary search runs in logarithmic
 140    /// time.
 141    /// <br/>
 142    /// Time Complexity = O(log(n)), Space Complexity = O(1), where n = number of items between
 143    /// <paramref name="fromIndex"/> and <paramref name="toIndex"/>.
 144    /// </remarks>
 145    public (int first, int last) Interval<T>(
 146        IEnumerable<T> source, T item, IComparer<T>? comparer = null, int? fromIndex = null, int? toIndex = null)
 102147    {
 102148        var first = First(source, item, comparer, fromIndex, toIndex);
 102149        if (first < 0)
 8150            return (-1, -1);
 151
 94152        var last = Last(source, item, comparer, first, toIndex);
 94153        return (first, last);
 102154    }
 155
 156    /// <inheritdoc path="//*[not(self::summary or self::remarks)]"/>
 157    /// <summary>
 158    ///     <inheritdoc/>
 159    ///     <br/>
 160    ///     This specific implementation assumes that <paramref name="source"/> is sorted in ascending order.
 161    /// </summary>
 162    /// <remarks>
 163    /// The algorithm first performs a binary search to find the index i of the 1st item. Then it checks whether
 164    /// the n-th occurrence of the item exists at index i + n, taking advantage of the fact that
 165    /// <paramref name="source"/> is sorted. The first step takes logarithmic time, whereas the second step takes
 166    /// constant time and space to execute.
 167    /// <br/>
 168    /// Time Complexity = O(log(n)), Space Complexity = O(1), where n = number of items between
 169    /// <paramref name="fromIndex"/> and <paramref name="toIndex"/>.
 170    /// </remarks>
 171    public int Nth<T>(
 172        IEnumerable<T> source, T item, int occurrenceRank, IComparer<T>? comparer = null, int? fromIndex = null,
 173        int? toIndex = null)
 281174    {
 281175        if (occurrenceRank < 0)
 1176            throw new ArgumentOutOfRangeException(nameof(occurrenceRank), "Must be a non-negative value.");
 177
 280178        comparer ??= Comparer<T>.Default;
 179
 280180        var first = First(source, item, comparer, fromIndex, toIndex);
 280181        if (first < 0)
 4182            return -1;
 183
 276184        var index = first + occurrenceRank;
 185
 276186        if (comparer.Compare(source.ElementAtO1OrDefault(index), item) == 0)
 270187            return index;
 6188        return -1;
 280189    }
 190}
Generated by: ReportGenerator 5.1.19.0
03/19/2023 - 17:28:50
GitHub | reportgenerator.io

Methods/Properties

Search(System.Collections.Generic.IEnumerable`1<T>,T,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>,System.Boolean)
First(System.Collections.Generic.IEnumerable`1<T>,T,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)
FirstAll(System.Collections.Generic.IEnumerable`1<T>,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)
Last(System.Collections.Generic.IEnumerable`1<T>,T,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)
Interval(System.Collections.Generic.IEnumerable`1<T>,T,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)
Nth(System.Collections.Generic.IEnumerable`1<T>,T,System.Int32,System.Collections.Generic.IComparer`1<T>,System.Nullable`1<System.Int32>,System.Nullable`1<System.Int32>)