8

List<T>アイテムが存在しない場合のBinarySearchメソッドについて混乱しています。

私が持っている

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

theList.BInarySearch(0)期待どおりに0をtheList.BInarySearch(3)返し、1を返します。

ただし、期待どおり-1ではなく-2theList.BinarySearch(1)を返します。MSDNマニュアルには、次のように記載されています。「戻り値：アイテムが見つかった場合は、並べ替えられたリスト内のアイテムのゼロベースのインデックス。それ以外の場合は、アイテムよりも大きい次の要素のインデックスのビット単位の補数である負の数。より大きな要素がない場合は、Countのビット単位の補数です。」

「ビット単位の補数」？私はここで何が欠けていますか、そしてそれはなぜtheList.BinarySearch(1) != -1ですか？

4

4 に答える 4

9

が存在し、戻り値はである必要があるtheList.BinarySearch(2)ため、あなたが話していると思います。10

ビット単位の補数演算子は、整数を否定するのと同じ効果を生み出しません。これが混乱の原因だと思います。いずれの場合も、検索結果を正確に分岐するために演算子がどのように機能するかを理解する必要はありません。質問のMSDN段落、および~~a = aがこのスニペットを直接暗示しているという事実：

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;
        ...
    }
}
于 2010-08-15T09:19:15.900 に答える
6

まず、なぜ-1を期待しますか？アイテムが最初のアイテムである場合、-0（整数の場合）返すことができないため、2番目のアイテムに対して-2が返されるのは当然です。

~-2次に、 -ビット単位のnot演算子を使用すると、適切なインデックスを簡単に取得できます。

于 2010-08-15T09:16:37.470 に答える
3

これらの負のインデックスを返す理由は、リストに見つからないアイテムの挿入をサポートするためです。この例では、インデックス= 2に2が挿入されます。それ以外の場合は、その位置を見つけるために別の二分探索を実行する必要があります。

于 2010-08-15T11:12:05.687 に答える
1

これを挿入ポイントに変換するには、ビット単位の補数を取ります。つまり、次のようになります。~retval

于 2010-08-15T09:15:36.383 に答える