Why is there a List<T>.BinarySearch(...)?

c# list collections binary-search
Water Cooler v2 picture Water Cooler v2 · Jul 15, 2010 · Viewed 9.8k times · Source

I'm looking at List and I see a BinarySearch method with a few overloads, and I can't help wondering if it makes sense at all to have a method like that in List?

Why would I want to do a binary search unless the list was sorted? And if the list wasn't sorted, calling the method would just be a waste of CPU time. What's the point of having that method on List?

Answer

Eric Lippert picture Eric Lippert · Jul 15, 2010

I note in addition to the other correct answers that binary search is surprisingly hard to write correctly. There are lots of corner cases and some tricky integer arithmetic. Since binary search is obviously a common operation on sorted lists, the BCL team did the world a service by writing the binary search algorithm correctly once rather than encouraging customers to all write their own binary search algorithm; a significant number of those customer-authored algorithms would be wrong.

Related questions

How to easily initialize a list of Tuples?

I love tuples. They allow you to quickly group relevant information together without having to write a struct or class for it. This is very useful while refactoring very localized code. Initializing a list of them however seems a bit …

Read More
How can I initialize a C# List in the same line I declare it. (IEnumerable string Collection Example)

I am writing my testcode and I do not want wo write: List<string> nameslist = new List<string>(); nameslist.Add("one"); nameslist.Add("two"); nameslist.Add("three"); I would love to write List<string> …

Read More
Convert List<DerivedClass> to List<BaseClass>

While we can inherit from base class/interface, why can't we declare a List<> using same class/interface? interface A { } class B : A { } class C : B { } class Test { static void Main(string[] args) { A a = new C(); // OK …

Read More