C# List <T> .BinarySearch valeur de retour lorsque la valeur n'est pas trouvée

Question

Je suis confus au sujet de la méthode BinarySearch de List<T> dans le cas où l'élément n'existe pas.

J'ai

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

theList.BInarySearch(0) renvoie 0, et theList.BInarySearch(3) renvoie 1, comme prévu.

Toutefois, theList.BinarySearch(1) renvoie -2, et non -1 comme je m'attendais. Le manuel MSDN dit: "Valeur de retour: l'index base zéro de l'élément dans la liste triée, si l'élément est trouvé, sinon, un nombre négatif qui est le complément binaire de l'index de l'élément suivant qui est plus grand que l'élément ou , s'il n'y a pas d'élément plus grand, le complément au nombre de bits de Count. "

Un "complément de bits"? Qu'est-ce que je manque ici et pourquoi est-ce que c'est theList.BinarySearch(1) != -1?

Answer 1

D'abord - pourquoi voudriez-vous attendre -1? Si l'élément est le premier élément, il ne peut pas renvoyer -0 (pour les entiers), il est donc logique que -2 soit renvoyé pour le second élément.

Ensuite, vous pouvez facilement obtenir le bon index en utilisant ~-2 - l'opérateur bitwise non.

Answer 2

pour le transformer en un point d'insertion, prendre le complément au niveau du bit, qui est la suivante: ~retval

Answer 3

Je suppose que vous parlez de theList.BinarySearch(2), car 1 existe et la valeur de retour doit être 0.

Le bitwise complement operator ne produit pas le même effet que la négation de l'entier, ce qui, je pense, est la source de votre confusion. Dans tous les cas, vous n'avez pas besoin de comprendre comment l'opérateur travaille correctement sur le résultat de la recherche. le paragraphe MSDN dans votre question, et le fait que ~~a = a, implique directement cet extrait:

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 raison pour le retour de ces indices négatifs est de soutenir l'insertion d'éléments qui ne figurent pas dans la liste. Dans cet exemple, 2 serait inséré à l'index = 2. Sinon, vous devrez effectuer une autre recherche binaire pour trouver cette position.