Usually, we use Array.BinarySearch to find a value in a sorted array, we all know that this method returns the index of the searched value in the array, if value is found. It turns out that the return value of BinarySearch is much more interesting and useful. Lets focus on what happens if the value is not found in the array.

Those who claim that if value is not found than a negative number will be returned, are absolutely right. But most of us don’t really know the whole truth about that negative number and how it can be used.


To understand its usage, we can see how the Add method in SortedList class is implemented (this operation must keep the list sorted):


   2: public virtual void Add(object key, object value)
   3: {
   4:     if (key == null)
   5:     {
   6:         throw new ArgumentNullException();
   7:     }
   8:     int index = Array.BinarySearch(this.keys, 0, this._size, key, this.comparer);
   9:     if (index >= 0)
  10:     {
  11:         throw new ArgumentException();
  12:     }
  13:     this.Insert(~index, key, value);
  14: }

Did you notice the bitwise complement operator~ in line 13? It is applied on the negative result of the binary search to produce an index that is used in the Insert method. The guys in Microsoft who wrote the SortedList.Add method took advantage of the following fact about BinarySearch return value:

If the array does not contain the searched value, the method returns a negative integer so you can apply the bitwise complement operator~ to it and produce an index. If this index is greater than or equal to the size of the array, the searched value is the largest number in the array. Otherwise, it is the index of the first element that is larger than the searched value.

So, the produced index can be used in the Insert method to add the value in the correct place and keep the array sorted. When I introduced this fact to some of my colleagues , they claimed this is very nice and tricky but may be unreadable. What do you say?

Tags :

6 Responses to “Operator~ and BinarySearch”

  1. Ruurd Boeke

    Said on May 1, 2008 :

    I vote it’s tricky as well. I do not like magical return values at all. They are not discoverable.

    Still, good find!

  2. bragi

    Said on May 2, 2008 :

    I think it’s a pretty cool trick that can save some lines of code and processing power. Some comment with the code is probably a wise thing to do for people who don’t know the trick.

  3. Jon von Gillern

    Said on May 5, 2008 :


  4. st0le

    Said on July 19, 2009 :

    I love this idea…

2 Trackback(s)

  1. May 2, 2008: Dew Drop - May 2, 2008 | Alvin Ashcraft's Morning Dew
  2. Jun 2, 2008: Finds of the Week - May 31, 2008 » Chinh Do

Post a Comment