C# -Liste <T> .BinarySearch Rückgabewert, wenn der Wert nicht gefunden wurde

Question

Ich bin verwirrt über die BinarySearch-Methode von List<T>, wenn das Element nicht existiert.

Ich habe

bekam

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

theList.BInarySearch(0) 0 zurück, und theList.BInarySearch(3) gibt 1 zurück, wie erwartet.

Allerdings theList.BinarySearch(1) gibt -2 zurück, und nicht -1, wie ich es erwarten würde. Das MSDN-Handbuch sagt: "Rückgabewert: Der nullbasierte Index des Elements in der sortierten Liste, wenn Element gefunden wird; andernfalls eine negative Zahl, die das bitweise Komplement des Index des nächsten Elements ist, das größer als Element oder ist , wenn es kein größeres Element gibt, das bitweise Komplement von Count. "

Ein "bitweises Komplement"? Was fehlt mir hier und warum ist das theList.BinarySearch(1) != -1?

Answer 1

Erste - warum sollte man -1 erwarten? Wenn der Artikel der erste Artikel ist, kann er -0 (für Integer) nicht zurückgeben, so dass der Grund -2 für den zweiten Artikel zurückgegeben wird.

Als nächstes können Sie leicht den richtigen Index mit ~-2 - der bitweisen nicht-Operator.

Answer 2

es zu einer Einfügemarke zu transformieren, das bitweise Komplement nehmen, das heißt: ~retval

Answer 3

Ich nehme an, Sie sprechen über theList.BinarySearch(2), weil 1 existiert und der Rückgabewert sollte 0 sein.

Die bitwise complement operator erzeugt nicht den gleichen Effekt wie die Negierung der Ganzzahl, was meiner Meinung nach die Quelle Ihrer Verwirrung ist. In jedem Fall müssen Sie nicht verstehen, wie der Operator arbeitet, um genau auf das Suchergebnis zu verzweigen. der MSDN Absatz in Frage, und die Tatsache, dass ~~a = a impliziert direkt mit diesem Schnipsel:

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

Der Grund, diese negative Indizes für die Rückgabe ist Einfügen von Elementen zu unterstützen, die nicht in die Liste gefunden. In diesem Beispiel würde 2 bei Index = 2 eingefügt werden. Andernfalls müssten Sie eine weitere binäre Suche durchführen, um diese Position zu finden.