// Returns the minimum index i in the range [0, list.Count — 1] such that list[i] > value — Upper
// Returns the minimum index i in the range [0, list.Count — 1] such that list[i] >= value — Lower

        private static void ValidateIndicesRange(int from, int to, int count)
        {
            ...
            Code.AssertArgument(to <= count, nameof(to),
                "The {0} index should not exceed the {1}", nameof(to), nameof(count));
            ...
        }

var index = Array.BinarySearch(data.BinarySearch(2);
if (index < 0)
{
  var insertIndex = ~index;
  ...
}

S>>Можно пример реального юз-кейза для этой штуки?

L>Ну и, в Google Code Jam иногда бывает полезно.

        [Test]
        public void Test001LowerBoundExample()
        {
            // важно: намекаем, что список должен быть отсортирован
            // важно: используем другой тип для значений, чтобы не спутать с индексами.
            var sortedData = new List<string> { "B", "C", "D", "F" };

            var indexOfLowerBound = sortedData.LowerBound("A");
            Assert.AreEqual(indexOfLowerBound, sortedData.IndexOf("B"));

            indexOfLowerBound = sortedData.LowerBound("B");
            Assert.AreEqual(indexOfLowerBound, sortedData.IndexOf("B"));

            indexOfLowerBound = sortedData.LowerBound("C");
            Assert.AreEqual(indexOfLowerBound, sortedData.IndexOf("C"));

            indexOfLowerBound = sortedData.LowerBound("E");
            Assert.AreEqual(indexOfLowerBound, sortedData.IndexOf("F"));

            indexOfLowerBound = sortedData.LowerBound("G");
            Assert.AreEqual(indexOfLowerBound, sortedData.Count);
        }

        [Test]
        public void Test002UpperBoundExample()
        {
            // важно: намекаем, что список должен быть отсортирован
            // важно: используем другой тип для значений, чтобы не спутать с индексами.
            var sortedData = new List<string> { "B", "C", "D", "F" };

            var indexOfUpperBound = sortedData.UpperBound("A");
            Assert.AreEqual(indexOfUpperBound, sortedData.IndexOf("B"));

            indexOfUpperBound = sortedData.UpperBound("B");
            Assert.AreEqual(indexOfUpperBound, sortedData.IndexOf("C"));

            indexOfUpperBound = sortedData.UpperBound("C");
            Assert.AreEqual(indexOfUpperBound, sortedData.IndexOf("D"));

            indexOfUpperBound = sortedData.UpperBound("E");
            Assert.AreEqual(indexOfUpperBound, sortedData.IndexOf("F"));

            indexOfUpperBound = sortedData.UpperBound("G");
            Assert.AreEqual(indexOfUpperBound, sortedData.Count);
        }

S>Чтобы принять решение надо бы написать реальный пример использования с этими параметрами и посмотреть, что будет лучше. Возьмёшься? Я могу придумать только такие, где вариант с startIndex + count выигрывает.

    //(1)
    var vBegin = verticals.LowerBound(horizontal.Begin, (x, v) => Comparer<double>.Default.Compare(x.Key, v));
    if (vBegin == verticalsCount)
    {
        continue;
    }

    //(2)
    var vEnd = verticals.UpperBound(horizontal.End, vBegin, verticalsCount, (x, v) => Comparer<double>.Default.Compare(x.Key, v));

    //(3)
    for (var vIndex = vBegin; vIndex < vEnd; ++vIndex)

S>С DisjointSets давай разберёмся после того, как добьём Lower/UpperBound()

Framework Design Principle: Frameworks must be designed starting from a set of usage scenarios and code samples implementing these scenarios.

        private static void Sample1()
        {
            var verticals = new List<KeyValuePair<double, string>>();
            var horizontal = new KeyValuePair<double, double>();

            //(1)
            var vBegin = verticals.LowerBound(
                horizontal.Key, (x, v) => Comparer<double>.Default.Compare(x.Key, v));
            if (vBegin == verticals.Count)
            {
                return;
            }

            //(2)
            var vEnd = verticals.UpperBound(
                horizontal.Key,
                vBegin, verticals.Count,
                (x, v) => Comparer<double>.Default.Compare(x.Key, v));

            //(3)
            for (var vIndex = vBegin; vIndex < vEnd; ++vIndex)
            {
                Console.WriteLine(verticals[vIndex]);
            }
        }

        private static void Sample2()
        {
            var verticals = new List<KeyValuePair<double, string>>();
            var horizontal = new KeyValuePair<double, double>();
            Func<KeyValuePair<double, string>, double, int> compare = (x, v) => Comparer<double>.Default.Compare(x.Key, v);

            //(1)
            var verticalsFrom = verticals.LowerBound(horizontal.Key, compare);
            if (verticalsFrom == verticals.Count)
            {
                return;
            }

            //(2)
            var verticalsTo = verticals.UpperBound(
                horizontal.Key,
                verticalsFrom, 
                verticals.Count - verticalsFrom,
                compare);

            //(3)
            for (var i = verticalsFrom; i < verticalsTo; ++i)
            {
                Console.WriteLine(verticals[i]);
            }
        }

        private static void Sample3()
        {
            var verticals = new List<KeyValuePair<double, string>>();
            var horizontal = new KeyValuePair<double, double>();
            Func<KeyValuePair<double, string>, double, int> compare = (x, v) => Comparer<double>.Default.Compare(x.Key, v);

            //(1)
            var verticalsFrom = verticals.IndexFrom(horizontal.Key, compare);
            if (verticalsFrom == verticals.Count)
            {
                return;
            }

            //(2)
            var verticalsTo = verticals.IndexTo(horizontal.Key, verticalsFrom, verticals.Count, compare);

            //(3)
            for (var i = verticalsFrom; i < verticalsTo; ++i)
            {
                Console.WriteLine(verticals[i]);
            }
        }

S>        private static void Sample3()
S>        {
S>            var verticals = new List<KeyValuePair<double, string>>();
S>            var horizontal = new KeyValuePair<double, double>();
S>            Func<KeyValuePair<double, string>, double, int> compare = (x, v) => Comparer<double>.Default.Compare(x.Key, v);

S>            //(1)
S>            var verticalsFrom = verticals.IndexFrom(horizontal.Key, compare);
S>            if (verticalsFrom == verticals.Count)
S>            {
S>                return;
S>            }

S>            //(2)
S>            var verticalsTo = verticals.IndexTo(horizontal.Key, verticalsFrom, verticals.Count, compare);

S>            //(3)
S>            for (var i = verticalsFrom; i < verticalsTo; ++i)
S>            {
S>                Console.WriteLine(verticals[i]);
S>            }
S>        }
S>

S>М?

S>Поскольку двигаемся маленькими шажками, то все изменения почти незаметны, но если сравнить с первоначальным вариантом — конфетка же

    var values = new List<int> { 2, 1, 7, 6, 4, 5 };
    values.Sort();
    const int valueToInsert = 3;
    var insertionPoint = values.LowerBound(valueToInsert);
    values.Insert(insertionPoint, valueToInsert);

S>Вопросы / предложения?

var something = collection.LocateNotLess(someValue); // huh?

KRZYSZTOF CWALINA We did not test the usability of the types in the System.IO namespace before shipping version 1.0 of the Framework.

Soon after shipping, we received negative customer feedback about System.IO usability.
We were quite surprised, and we decided to conduct usability studies with eight average VB developers. Eight out of eight failed to read text from a file in the 30 minutes we allocated for the task. We believe this was due in part to problems with the documentation search engine and insufficient sample coverage; however, it is clear that the API itself had several usability problems. If we had conducted the studies before shipping the product, we could have eliminated a significant source of customer dissatisfaction and avoided the cost of trying to fix the API of a major feature area without introducing breaking changes.

BRAD ABRAMS There is no more powerful experience to give an API designer a visceral understanding of the usability of his or her API than sitting behind a one-way mirror watching developer after developer get frustrated with an API he or she designed and ultimately fail to complete the task.

I personally went through a full range of emotions while watching the usability studies for System.IO that we did right after shipping version 1.0. As developer after developer failed to complete the simple task, my emotions moved from arrogance to disbelief, then to frustration, and finally to stringent resolve to fix the problem in the API.

L>Один я тебе привел уже — нахождение позиции для вставки. Все 4 не осилю. PartitionPoint вообще не разу не использовал

00000000000000000000000000000111111111111111111111111
                             ^ partition_point

S>Ок, допустим неудобно настолько, что мы забиваем на least surprise. Зачем тогда to может быть равен count? это ж индекс типа. Я вот про это:

00000000000000000000000000000111111111111111111111111
^first                       ^ partition_point       ^second

template<typename I, typename P>
I find_if(I first, I last, P pred)
{
    while (first != last && !pred(*first))
        ++first;
    return first;
}

S>Дак выяснили, обсудили и закрыли тему уже

https://msdn.microsoft.com/ru-ru/library/w4e7fxsh(v=vs.110).aspx
The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.
...
If the List<T> contains more than one element with the same value, the method returns only one of the occurrences, and it might return any one of the occurrences, not necessarily the first one.

S>И в итоге выбор у нас получается такой: или вот такой вот компромисс, или вообще убирать методы. Т.е. вот такой вот компромисс

var items = LoadItems().OrderBy(item => item.ID).ToList();
...
TItem item10;
if (items.TryBinarySearchItem(item => item.ID, 10, out item10)
{

}

var comparer = (item, id) => item.ID - id;
var index = items.LowerBound(10, comparer);
if (index != items.Count && items[index].ID == 10)
{
    // есть значение
}
else
{
    // нет значения
}

public static int BinarySearch<T,TValue>(this IList<T> list, TValue value, Func<T, TValue, int> comparer);

public static bool TryBinarySearch<T,TValue>(this IList<T> list, Func<T, TValue> projection, TValue value, out T result)
{
    var comparer = (item, value) => Comparer<TValue>.Default.Compare(projection(item), value);
    var index = list.BinarySearch(value, comparer);
    if (index != list.Count)
    {
        result = list[index];
        return true;
    }
    result = default(T);
    return false;
}

J>var items = LoadItems().OrderBy(item => item.ID).ToList();
J>...
J>TItem item10;
J>if (items.TryBinarySearchItem(item => item.ID, 10, out item10)
J>{

J>}
J>

if(auto x = binary_search(xs, value))
{
    // ...
}