当前位置：文江博客话题详情

C# 二分查找变体

发布于 2024-08-15 19:15:47 字数 355 浏览 4 评论 0原文

列表已排序。

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

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

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

例如：T.StartIndex= 100

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

我该怎么做？

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

离旧人 2024-08-22 19:15:47

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

If you use List<T>.BinarySearch then it will find the exact position of one exists, or return the bitwise complement of the index at which you would need to insert the item.

So if it returns a negative number, just check the next and previous items (being careful of the ends of course) to see whether either of those is within your desired tolerance.

For example:

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

回复收藏 0 原文

~没有更多了~