C#中List<T>.BinarySearch方法在未找到值时返回的值是什么？

Question

当使用List<T>的BinarySearch方法查找一个不存在的元素时，我感到困惑。

我已经得到：

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

theList.BInarySearch(0) 返回0，theList.BInarySearch(3) 返回1，符合预期。

然而，theList.BinarySearch(1) 返回-2，而不是我期望的-1。MSDN手册说： "返回值：如果找到item，则为已排序List中item的基于零的索引；否则，它是比item大的下一个元素的索引的按位补数，或者如果没有更大的元素，则是Count的按位补数。"

“按位补数”？我错过了什么，为什么theList.BinarySearch(1) != -1 ？

- user335023

---

我猜你是在寻找 theList.BinarySearch(2) 吧？1 就在那里... - Kobi

按位取反是指得到给定数字的每一位上均取反的数字。00110101 = ~ 11001010。它类似于逻辑非操作，但 ! 对整个值执行逻辑非操作，而 ~ 对每个位执行逻辑非操作。 - Jon Hanna

Answer 1

我假设你所说的是theList.BinarySearch(2)，因为1已存在且返回值应该是0。 按位求反运算符与对整数求负不产生相同的效果，这可能是你困惑的根源。无论如何，你不需要理解运算符的工作原理就能准确地对搜索结果进行分支；你问题中的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;
        ...
    }
}

- Ani

Answer 2

首先，你为什么会期望返回-1呢？如果这个项目是第一个项目，它不能返回整数的-0，所以理所当然的，第二个项目将返回-2。

其次，你可以使用位非运算符~-2轻松获取正确的索引。

- Kobi

Answer 3

返回负索引的原因是为了支持向列表中插入未找到的项目。在这个例子中，2将被插入到索引=2的位置。否则，您需要执行另一个二分查找来找到该位置。

- bbudge

---

有趣的是，我一直在想那个位补码有什么用...文档中的解释相当晦涩。 - Thomas Levesque

Answer 4

要将其转换为插入点，请取位补，即：~retval

- corvuscorax