C# List.BinarySearch 在未找到值时返回值

发布于 2024-09-14 17:57:15 字数 519 浏览 10 评论 0原文

当该项目不存在时，我对 List 的 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 ？

原文

I am confused about the BinarySearch method of List<T> in case when the item does not exist.

I've got

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

theList.BInarySearch(0) returns 0, and theList.BInarySearch(3) returns 1, as expected.

However, theList.BinarySearch(1) returns -2, and not -1 as I'd expect. The MSDN manual says:
"Return value: The zero-based index of item in the sorted List, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count."

A "bitwise complement"? What Am I missing here and why is it that theList.BinarySearch(1) != -1 ?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一身骄傲 2024-09-21 17:57:15

我假设您正在谈论 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;
        ...
    }
}

I assume you are talking about theList.BinarySearch(2), because 1 exists and the return value should be 0.

The bitwise complement operator does not produce the same effect as negating the integer, which I think is the source of your confusion. In any case, you do not need to understand how the operator works to accurately branch on the search-result; the MSDN paragraph in your question, and the fact that ~~a = a, directly implies this snippet:

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

回复收藏 0 原文