Runtime: [API] Array and List have BinarySearch, but SortedList does not. This seems illogical.

[Ark-kun]

Binary search should be performed on an ordered list of items.
Thus it's a natural operation for SortedList and not so natural for Array or List as they may be non-ordered causing BinarySearch to return incorrect answer.

BCL should either add BinarySearch to SortedList or better yet make am extension method for IList.

[jnm2]

See https://github.com/dotnet/corefx/issues/4697

[sharwell]

SortedList<TKey, TValue> does not implement IList<T>. This leads to some interesting side effects. The most interesting of these is due to the fact duplicate keys are not allowed in this type. Therefore, BinarySearch ends up exposed as SortedList<TKey, TValue>.IndexOfKey.

I have an API proposal in a standalone library to add a SortedTreeList<T> type which behaves as a proper "sorted list" (tunnelvisionlabs/dotnet-trees#19). This type does allow duplicate items, so IndexOf, LastIndexOf, and BinarySearch are three distinct operations. The first two still do a binary search, but unlike BinarySearch the result is deterministic for the case of duplicates.

[Ark-kun]

Therefore, BinarySearch ends up exposed as SortedList.IndexOfKey.

This is not the case unfortunately. I looked at the sources and fooled myself for a second too.
The reason IndexOfKey is not BinarySearch is that it always returns -1 when the element is not found while BinarySearch returns the "complemented" index where that element would end up if inserted.

So IndexOfKey is BinarySearch with half of the useful properties stripped.
http://referencesource.microsoft.com/#System/compmod/system/collections/generic/sortedlist.cs,584

[safern]

@Ark-kun thanks for your suggestion, could you please do a formal API-Proposal so that @ianhays and me take a look and make a decision if it is good enough to send it to review?

Here is an example of an API proposal: https://github.com/dotnet/corefx/issues/24445

[stephentoub]

No API proposal in almost two years. Closing.