C＃二进制搜索变化

2009-12-29 98 views 0 likes

该列表已分类。C＃二进制搜索变化

我有一个列表，我想对它进行二分搜索。 T有像StartIndex，EndIndex等成员

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

我需要扭转这一点，如下所示：我想找到一个StartIndex可能OffBy一个小值。

例如：T.StartIndex = 100

如果输入是101和OffBy 1然后BinarySearch的应返回该对象。

我该怎么做？

顺便说一句，我问如何与默认的二进制搜索方法列表有。这是我感兴趣的，对定制的二分查找实现不感兴趣。

来源

2009-12-29 DarthVader

为了执行二进制搜索，列表需要进行排序，但你在任何地方不mantion说。 – 2009-12-29 07:33:47

我刚刚做过...... – DarthVader 2009-12-29 07:35:11

是啊米奇......前4个单词。 – mpen 2009-12-29 07:46:19

回答

如果您使用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

来源

2009-12-29 07:43:42

我会买。谢谢。 – DarthVader 2009-12-29 07:47:20

C＃二进制搜索变化

回答

相关问题