C#二进制搜索变体

Question

列表已排序.

我有一个List,我想对它进行二分搜索.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