C# 二进制搜索变体

Question

列表已排序。

我有一个列表，我想对其进行二分查找。 T 有 StartIndex、EndIndex 等成员。

我可以使用 StartIndex 在列表上进行二进制搜索，即:我已经为此实现了 IComparable。

我需要稍微扭曲一下，如下所示:我想找到一个可能是 OffBy 的小值的 StartIndex。

例如:T.StartIndex= 100

如果输入为 101 且 OffBy 为 1，则 BinarySearch 应返回此对象。

我该怎么做？

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

Answer 1

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

因此，如果它返回负数，只需检查下一项和上一项(当然要注意结尾)，看看其中一项是否在您期望的容差范围内。

例如:

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