Has C# something like C++ std::equal_range?

Question

I have been searching and did not really find an answer. To be honest, I think that there is really a little of information for usage of this function in the internet. The reference itself isn't clear enough for me to find an equivalent in C#.

I have to port a C++ class to C#. The old C++ class uses this function at one point and I replaced it with the usage of LinQ using Where(), which is provided by enumerable objects:

std::equal_range(it_begin, it_end, value, comparer)
//changes to
list.Where(/*some comparison using the same comparison logic and the value like C++ version*/)

Unfortunatelly I don't get the same ranges like in the original code. So I'm wondering if I replaced the C++-Method with the correct equivalent or if I have some logic-errors in my comparison code.

So what is the correct equivalent of std::equal_range in C#? Is my solution the right one or is the equivalent something totally different?

Edit:

Thanks for the hint to say something to the C++ function.

First here is the documentation

After all as far as I understand it, I returns a range of a list which contains all values which are like the given value. A User can provide a comparer where I'm not completely sure for what this is used: - to compare the values in the list with the given value? - to compare for the sorted result?

Edit2:

The reason for my different results was located somewhere else. So considering the complexity criteria I've accepted Matthews answer. Allthough considering the result all 3 solutions (Matthews, Renés and mine) deliver the same result. So if performance doesn't matter and/or less code is wished, maybe one of the other solutions will be OK for you.

Answer 1

You can solve this with binary search.

This is essentially an identical implementation to equal_range(), and therefore has the same complexitity of ~O(Log2(N):

(Implementation of lower and upper bound stolen from here...)

using System;
using System.Collections.Generic;

namespace Demo
{
    class Program
    {
        static void Main()
        {
            var values = new List<string>{"1", "2", "3", "5", "5", "5", "7", "8", "9"};

            test(values, "5");
            test(values, "-");
            test(values, "A");
            test(values, "4");
            test(values, "6");
        }

        public static void test<T>(IList<T> values, T target) where T: IComparable<T>
        {
            var range = EqualRange(values, target);
            Console.WriteLine($"Range for {target} is [{range.Item1}, {range.Item2})");
        }

        public static Tuple<int, int> EqualRange<T>(IList<T> values, T target) where T : IComparable<T>
        {
            int lowerBound = LowerBound(values, target, 0, values.Count);
            int upperBound = UpperBound(values, target, lowerBound, values.Count);

            return new Tuple<int, int>(lowerBound, upperBound);
        }

        public static int LowerBound<T>(IList<T> values, T target, int first, int last) where T: IComparable<T>
        {
            int left  = first;
            int right = last;

            while (left < right)
            {
                int mid = left + (right - left)/2;
                var middle = values[mid];

                if (middle.CompareTo(target) < 0)
                    left = mid + 1;
                else
                    right = mid;
            }

            return left;
        }

        public static int UpperBound<T>(IList<T> values, T target, int first, int last) where T : IComparable<T>
        {
            int left  = first;
            int right = last;

            while (left < right)
            {
                int mid = left + (right - left) / 2;
                var middle = values[mid];

                if (middle.CompareTo(target) > 0)
                    right = mid;
                else
                    left = mid + 1;
            }

            return left;
        }
    }
}