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 ?

Answer 1

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