0

リストがソートされます。

私はリストを持っていて、その上で二分探索をしたいと思っています。T には、StartIndex、EndIndex などのメンバーがあります。

StartIndex を使用して、リストに対してバイナリ検索を実行できます。つまり、このために IComparable を実装しました。

これを次のように少しひねる必要があります: OffBy の値が小さい StartIndex を見つけたいとします。

例: T.StartIndex= 100

入力が 101 で OffBy 1 の場合、BinarySearch はこのオブジェクトを返す必要があります。

これどうやってするの？

ところで、リストが持っているデフォルトのバイナリ検索方法でこれを行う方法を尋ねています。カスタムバイナリ検索の実装には興味がありません。

4

1 に答える 1

6

を使用する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-29T07:43:42.450 に答える