Bit Flipping the Binary Search Result

Sunday, October 9, 2005

When I did the Atlas hands on lab weeks ago, the following piece of code jumped out at me:

int index = Array.BinarySearch(

       autoCompleteWordList,

       prefixText,

       new CaseInsensitiveComparer()

   );

 

if (index < 0)

{

    index = ~index;

}

Why is the code doing a bitwise complement (~) on the return value of BinarySearch?

My next stop was the documentation for the return value of Array.BinarySearch, which states:

The index of the specified value in the specified array, if value is found. If value is not found and value is less than one or more elements in array, a negative number which is the bitwise complement of the index of the first element that is larger than value

In other words, if you don’t find an exact match you can flip all the bits and have an index pointing to something close – a good trick to know when building an auto-complete control.


Comments
Milan Negovan Monday, October 10, 2005
What documentation misses is a hint that the array should be sorted first. Otherwise the bit complement might not give you an accurate position index. I've been bitten by this before.
Scott Mitchell Friday, October 14, 2005
Milan, if you don't have a sorted array, BinarySearch is not going to work (unless you're lucky), let alone be able to have it's bit complement return a 'close estimate.'
Comments are now closed.
by K. Scott Allen K.Scott Allen
My Pluralsight Courses
The Podcast!