C# List <T> .BinarySearch valor de retorno cuando no se encuentra el valor

Question

Estoy confundido acerca del método BinarySearch de List<T> en caso de que el elemento no exista.

Tengo

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

theList.BInarySearch(0) devuelve 0, y theList.BInarySearch(3) devuelve 1, como se esperaba. Sin embargo, theList.BinarySearch(1) devuelve -2, y no -1 como era de esperar. El manual de MSDN dice: "Valor de retorno: El índice basado en cero del artículo en la Lista ordenada, si se encuentra un elemento; de lo contrario, un número negativo que es el complemento bit a bit del índice del siguiente elemento que es más grande que el elemento o , si no hay un elemento más grande, el complemento bit a bit de Count ".

¿Un "complemento bit a bit"? ¿Qué me estoy perdiendo aquí y por qué es que theList.BinarySearch(1) != -1?

Answer 1

Primera - ¿por qué esperar -1? Si el artículo es el primero, no puede devolver -0 (para enteros), por lo que es razonable que se devuelva -2 para el segundo artículo.

A continuación, puede obtener fácilmente el índice correcto utilizando ~-2 - el operador bit a bit no.

Answer 2

para transformarlo a un punto de inserción, tomar el complemento bit a bit, es decir: ~retval

Answer 3

Supongo que está hablando de theList.BinarySearch(2), porque 1 existe y el valor de retorno debe ser 0.

El bitwise complement operator no produce el mismo efecto que negar el entero, que creo que es el origen de su confusión. En cualquier caso, no necesita comprender cómo funciona el operador para bifurcar con precisión en el resultado de la búsqueda; el párrafo MSDN en su pregunta, y el hecho de que ~~a = a, implica directamente este fragmento:

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

La razón para el retorno de estos índices negativos es apoyar la inserción de artículos que no se encuentran en la lista. En este ejemplo, 2 se insertarían en el índice = 2. De lo contrario, tendría que realizar otra búsqueda binaria para encontrar esa posición.