C# Binary Searching a List
Binary Search
Binary searching is a powerful method to quickly find a value from a sorted list. There are data structures, such as binary search trees, that specialize in providing an implementation that makes binary searching easy to do. However binary searching can be done on regular List data structures.
Binary Search is such a powerful and useful technique that it is built-in into the .NET Framework.
What is Binary Search
First and foremost, Binary Search only works on sorted lists of elements. Consequently elements in the list must be comparable. In other words, given two elements inside the least, there should be some way to determine which is smaller or greater than the other.
Binary search works by starting at the middle of the list. The element in the middle is compared to the "target" value we are looking for. (Note that this may be a value that we want to check if it exists at all inside the list). If the target value is equal to the middle element, we are done.
Otherwise, if the target value is smaller than the middle element, we look from now on to only elements on the left of the middle value. Alternatively, if the target value is larger than the middle element, we look to only elements to the right.
We can safely throw away half of the list because the list is sorted. If the target value is smaller than the "half way" element, because the list is sorted, any element after that middle element will also be bigger, and thus guaranteed not equal.
The same procedure is repeated on the new list segment over and over until we either find the value, or the list runs out.
Advantage of Binary Search
Binary search is advantageous because it is extremely fast. Each comparison allows us to rule-out an entire half of the list. Binary search in C# is especially a must if you know ahead of time that the list will be sorted.
If the list is not sorted already, you might want to sort it just to be able to use Binary Search. But be careful, this is only good in the long run if you have to sort once and do a bunch of searches. If you have to sort every time you search, then something like IndexOf is better.
Binary Search in C#
Binary search in C# is very easy. Given any ArrayList or List, instead of calling the IndexOf function to get the index of a target value, call BinarySearch. The BinarySearch function returns an integer index that will be exactly the same as IndexOf if the element is found. The only difference is IndexOf returns -1 when the element is not found, BinarySearch can return any sort of negative number.
Conclusion
In conclusion, binary search in C# is extremely fast when searching sorted lists. Given the right circumstances it is even worth it to sort first and then perform searches.