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 回答