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

Question

I've read about 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!

Answer 1

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.

Answer 2

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.

Answer 3

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.