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

Question

I am confused about the BinarySearch method of List 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 ?

Answer 1

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

Answer 2

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.

Answer 3

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;
        ...
    }
}

Answer 4

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.