Tuesday, July 17, 2012

List<T>.BinarySearch Pitfalls

The BinarySearch Method of List collection can be very useful to get the zero-based index of an element.
Further more if the element you searched for is not in the List you can calculate the index of the first element that is larger then the element you searched for. Just apply the ~ operator on the result of the BinarySearch:
var pos = aList.BinarySearch(aString);
if (pos < 0)
{
    aList.Insert(~pos, aString);
}

But there is one pitfall: The List must already be sorted; otherwise the BinerySearch result is incorrect.
This is not a big secret. It is clearly stated in the MSDN description for the Method (under Remarks)

I saw a Bug in a Project where someone used a BinarySearch to find duplicated entries between to Lists. This works as long as the Lists are sorted. If not the result is totally nonsense.
It took a while to find this Bug.
MSDN Link:
http://msdn.microsoft.com/en-us/library/w4e7fxsh.aspx

No comments:

Post a Comment