当找不到值时,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手册说:"返回值:排序列表中项目的从零开始的索引,如果找到项目;否则,是负数,它是下一个元素的索引的按位补码,大于项目或,如果没有更大的元素,则为Count的按位补码."

一个"按位补码"？我在这里错过了什么,为什么会这样theList.BinarySearch(1) != -1？

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;
        ...
    }
}

Answer 2

首先 - 你为什么期望-1？如果该项目是第一项,则它不能返回-0(对于整数),因此对于第二项,将返回原因-2.

接下来,您可以使用~-2- 按位运算符轻松获得正确的索引.