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?