C# List <T> .BinarySearch restituisce il valore quando il valore non viene trovato

Question

Sono confuso circa il metodo BinarySearch di List<T> nel caso in cui l'elemento non esiste.

Ho

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

theList.BInarySearch(0) restituisce 0, e theList.BInarySearch(3) restituisce 1, come previsto.

Tuttavia, theList.BinarySearch(1) restituisce -2 e non -1 come mi aspetto. Il manuale MSDN dice: "Valore di ritorno: l'indice a base zero di un elemento nell'elenco ordinato, se viene trovato un elemento, altrimenti un numero negativo che è il complemento bit a bit dell'indice dell'elemento successivo più grande di un articolo o , se non c'è un elemento più grande, il complemento bit per bit di Count. "

Un "complemento bit per bit"? Cosa mi manca qui e perché è il theList.BinarySearch(1) != -1?

Answer 1

In primo luogo - il motivo per cui ci si può aspettare -1? Se l'articolo è il primo elemento, non può restituire -0 (per i numeri interi), quindi rimane valido il motivo -2 verrà restituito per il secondo elemento.

Successivamente, è possibile ottenere facilmente l'indice corretto utilizzando ~-2 - l'operatore non bit per bit.

Answer 2

Per trasformarlo in un punto di inserimento, prendere il complemento bit a bit, vale a dire: ~retval

Answer 3

Suppongo che stiate parlando di theList.BinarySearch(2), perché 1 esiste e il valore restituito deve essere 0.

Il bitwise complement operator non produce lo stesso effetto della negazione dell'intero, che ritengo sia la fonte della vostra confusione. In ogni caso, non è necessario capire come l'operatore lavora per ramificarsi accuratamente sul risultato della ricerca; il comma MSDN nella sua interrogazione, e il fatto che ~~a = a, implica direttamente questo frammento:

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

Il motivo per la restituzione di questi indici negativi è quello di sostenere l'inserimento di elementi che non si trovano nella lista. In questo esempio, 2 verrebbe inserito in index = 2. Altrimenti, dovresti eseguire un'altra ricerca binaria per trovare quella posizione.