c# - C# 二分搜索变体

Question

列表已排序。

我有一个列表，我想对其进行二进制搜索。T 有 StartIndex、EndIndex 等成员。

我可以使用 StartIndex 对列表进行二进制搜索，即：我为此实现了 IComparable。

我需要将其稍微扭曲如下：我想找到一个可能是 OffBy 小值的 StartIndex。

例如：T.StartIndex= 100

如果输入是 101 并且 OffBy 1 那么 BinarySearch 应该返回这个对象。

我怎样才能做到这一点？

顺便说一句，我问如何使用 List 具有的默认二进制搜索方法。这就是我感兴趣的，对自定义二进制搜索实现不感兴趣。

Answer 1

如果您使用List<T>.BinarySearchthen 它将找到存在的确切位置，或者返回您需要插入项目的索引的按位补码。

因此，如果它返回一个负数，只需检查下一项和上一项（当然要注意结尾），看看其中任何一项是否在您想要的公差范围内。

例如：

int index = list.BinarySearch(item);
if (index < 0)
{
    int candidate = ~index;
    if (candidate > 0 && 
        Math.Abs(list[candidate - 1].StartIndex - item.StartIndex) <= tolerance)
    {
        index = candidate - 1;
    }
    else if (candidate < list.Count - 1 && 
         Math.Abs(list[candidate + 1].StartIndex - item.StartIndex) <= tolerance)
    {
         index = candidate + 1;
    }
    else
    {
         // Do whatever you need to in the failure case
    }
}
// By now, index is correct