In a .NET/C# context, what is a binary search and how/why can I use one?

I've read abo开发者_开发知识库ut binary searches on Wikipedia for the first time today and just skimmed the surface a bit. It seems it's used to find items in a collection quickly where memory is sparse.

In a .NET/C# context, would I ever need to use one? Do you ever use them while building production actual-real-world software?

I'm sorry if this questions comes off as inciting, but I'm asking a genuine question as a student!

List<T> has a BinarySearch method, as does Array. You would use them if you had a sorted list and needed to find an element. Because they return an index, you can do things you can't with a straight dictionary like find the largest element less than a key.

One place I've used a binary search in real-world software is for doing range searches. Shipping rates are given for weight range, so there might be one rate for 0-1 lb, one for 1-5 lb, and one for 5-10 lb. If I call List<T>.BinarySearch and look for 4 lb, it will give me the first index higher than 4 lb, which I can use the find the 1-5 lb range. A dictionary would just tell me that 4 lb was not found.

For general sorted data, you are often better off using SortedList or SortedDictionary.

Binary searches only work on sorted data, so as long as you have some collection of data in C# that you know is sorted, you can do a binary search on it. Your best bet would be to use the implementations that are already provided (such as List<T>.BinarySearch()), but if the particular collection you're using doesn't have a binary search method, you can always write one.

Here's an example using the built in libraries:

// An ordered list of ints
List<int> ints = new List<int>() { 1, 4, 8, 20, 30, 44 };

// Search for 5 in the list
int ix = ints.BinarySearch(8);

// Display the index the element 8 was found at
Console.WriteLine(ix);

And yes, you would definitely want to use a binary search when you're searching sorted data.

Sometime ago (while I was a student in the Computer Engineering course) I had to work with search algorithms. The result of such coursework was a paper.

I posted on my blog about Quicksort and Binary Search algorithms in C++. Although it's in C++ code it should provide you with the how/why to use binary search. It also shows how to implement the binary search algorithm. There's a sample application provided so that you can test it by yourself.