C# List<T>.BinarySearch return value when value not found

Question

I am confused about the BinarySearch method of List<T> in case when the item does not exist.

I've got

List<long> theList = {1, 3, 5, ...}.

theList.BInarySearch(0) returns 0, and theList.BInarySearch(3) returns 1, as expected.

However, theList.BinarySearch(1) returns -2, and not -1 as I'd expect. The MSDN manual says: "Return value: The zero-based index of item in the sorted List, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count."

A "bitwise complement"? What Am I missing here and why is it that theList.BinarySearch(1) != -1 ?

Reconstructionist

I suppose you're searching for theList.BinarySearch(2)? 1 is right there... – Keavy

Bitwise complement is simply a number which is the complement of each bit of the first number. 00110101 = ~ 11001010. It's like a not operation, but where ! does a boolean not on the whole value, ~ does a not on each bit. – Nerty

Answer 1

First - why would you expect -1? If the item is the first item, it cannot return -0 (for integers), so it stands to reason -2 will be returned for the second item.

Next, you can easily get the right index by using ~-2 - the bitwise not operator.

Keavy

Answer 2

I assume you are talking about theList.BinarySearch(2), because 1 exists and the return value should be 0.

The bitwise complement operator does not produce the same effect as negating the integer, which I think is the source of your confusion. In any case, you do not need to understand how the operator works to accurately branch on the search-result; the MSDN paragraph in your question, and the fact that ~~a = a, directly implies this snippet:

int index = theList.BinarySearch(num);

if (index >= 0)
{
    //exists
    ...
}
else
{
    // doesn't exist
    int indexOfBiggerNeighbour = ~index; //bitwise complement of the return value

    if (indexOfBiggerNeighbour == theList.Count)
    {
        // bigger than all elements
        ...
    }

    else if (indexOfBiggerNeighbour == 0)
    {
        // smaller than all elements
        ...
    }

    else
    {
        // Between 2 elements
        int indexOfSmallerNeighbour = indexOfBiggerNeighbour - 1;
        ...
    }
}

Ahriman

Answer 3

The reason for returning these negative indices is to support inserting items that are not found into the list. In this example, 2 would be inserted at index = 2. Otherwise, you would have to perform another binary search to find that position.

Jaquelinejaquelyn

Interesting, I was wondering what was the use of that bitwise complement... the explanation in the documentation is quite obscure – Killy

Answer 4

To transform it to an insertion point, take the bitwise complement, that is: ~retval

Eustis