为什么 BinarySearch 使用 ~ 运算符来 return 一个负数？

Question

在this code, there is a binary-search algorithm. To signal that the item is not found, a negative number is returned, which in the code is done with return ~mid (see line 92).

public int Search(string name)
{
    int low = 0;
    int high = _sortedPositions.Count - 1;
    int mid = 0;
    while (low <= high)
    {
        mid = (low + high) >> 1;
        _stream.Position = _sortedPositions[mid];
        var curName = _br.ReadString();
        var comp = string.Compare(name, curName);
        if (comp == 0)
            return mid;
        if (comp < 0)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return ~mid;
}

我的问题是：为什么要这样做？返回一个固定的负整数有什么优势，比如 return -1?

Answer 1

是的，有一个好处 （如果函数 return 的值正确，但事实并非如此，请参阅下文）。

负数表示在集合中找不到要搜索的键，就像returning -1 .

然而，与简单地 returning -1 相比，您获得的是您可以再次翻转此负值的位以取回值 应该所在的索引如果要遵循排序顺序，则为。

你可以这样使用它：

int index = Search("Some name");
if (index < 0)
    // insert at position (~index)

现在，这个特定的搜索功能有一个缺陷，它会在找到要比较的最后一个项目的边界情况下错误地报告错误的索引，但它搜索的名称应该是在此项之后。

例如，尝试在搜索函数报告的位置中添加以下两个字符串：A 然后是 Z.

它会以错误的顺序添加它们，Z 在 A 之前。

原因是它找到了应该在索引 0 处比较的单个项目 A，但是 Z 应该添加在之后索引 0，而不是在索引 0.

但是，这个错误的修复很简单：

将 mid 的初始计算移到循环外
... 并在更改 low 或 high

这样最终的 mid 值将是正确的。这是最终函数：

public int Search(string name)
{
    int low = 0;
    int high = _sortedPositions.Count - 1;
    int mid = low + (high - low) / 2;                  // note #2
    while (low <= high)
    {
        var curName = _sortedPositions[mid];           // note #1
        var comp = string.Compare(name, curName);
        if (comp == 0)
            return mid;
        if (comp < 0)
            high = mid - 1;
        else
            low = mid + 1;
        mid = low + (high - low) / 2;                  // note #2
    }
    return ~mid;
}

（注意 #1：我在探索您的代码以使其成为运行时将 sortedPositions 切换为简单的 List<string>。显然这将是与基于流的示例不同。）

(注#2：我计算 mid 值的方法是计算差值并除以 2，这是建议的方法。如果集合有这么多low + high 会溢出的值，建议的方法不会。）

许多实现采用的更简单的修复方法是，在您没有更多项目可看的地方，low == mid（进行上述更改），因此针对该错误的不同修复方法是到 return ~low 而不是 ~mid，然后必须执行最小的更改：

public int Search(string name)
{
    int low = 0;
    int high = _sortedPositions.Count - 1;
    int mid;
    while (low <= high)
    {
        mid = low + (high - low) / 2;                  // note #2
        var curName = _sortedPositions[mid];           // note #1
        var comp = string.Compare(name, curName);
        if (comp == 0)
            return mid;
        if (comp < 0)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return ~low;
}

为什么 BinarySearch 使用 ~ 运算符来 return 一个负数？

Why does BinarySearch use ~ operator to return a negative number?

c#

bitwise-operators

binary-search