8

List<T>如果项目不存在，我对 BinarySearch 方法感到困惑。

我有

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

theList.BInarySearch(0)返回 0，并按theList.BInarySearch(3)预期返回 1。

但是，theList.BinarySearch(1)返回-2，而不是我期望的 -1 。MSDN手册说：“返回值：如果找到项目，则排序列表中项目的从零开始的索引；否则，一个负数，它是大于项目的下一个元素的索引的按位补码，或者，如果没有更大的元素，Count 的按位补码。”

“按位补码”？我在这里错过了什么，为什么会这样theList.BinarySearch(1) != -1？

4

4 回答 4

9

我假设你在谈论theList.BinarySearch(2)，因为1存在并且返回值应该是0。

按位补码运算符不会产生与否定整数相同的效果，我认为这是您困惑的根源。在任何情况下，您都不需要了解运算符如何准确地根据搜索结果进行分支；~~a = a您问题中的 MSDN 段落，以及, 直接暗示此片段的事实：

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- 位非运算符轻松获得正确的索引。

于 2010-08-15T09:16:37.470 回答
3

返回这些负索引的原因是为了支持将未找到的项目插入到列表中。在此示例中，2 将插入到 index = 2 处。否则，您将不得不执行另一次二分搜索来找到该位置。

于 2010-08-15T11:12:05.687 回答
1

要将其转换为插入点，请采用按位补码，即：~retval

于 2010-08-15T09:15:36.383 回答