[C#] lower_bound, upper_bound を実装する方法(二分探索)

lower_bound と upper_bound

lower_bound と upper_bound という2つの関数があります。これは C++ のSTLライブラリにある関数です。この関数を C# で実装していきます。

lower_bound – cpprefjp C++日本語リファレンス

upper_bound – cpprefjp C++日本語リファレンス

これらの関数は、ソート済のデータに対して、指定された要素がどのあたりに現れるかをいい感じに取得できるようにする関数です。二分探索をしながらより詳しい情報を得られる関数です。

C# には二分探索(バイナリサーチ)は標準ライブラリに実装されていますが、lower_bound と upper_bound は実装されていません。

lower_bound と upper_bound では、キーに一致する要素が存在しない場合でも、イテレータで結果を返します。

lower_bound と upper_bound の違いは以下の通りです。

lower_bound

lower_bound は「指定された要素以上の値が現れる最初の位置のイテレータを取得する」

例えば [1, 1, 2, 3, 3, 4] というソート済の配列に対して3以上の要素がどこから始まるかを知りたいときに使います。結果は 3 です。

upper_bound

upper_bound は「指定された要素より大きい値が現れる最初の位置のイテレータを取得する」

例えば [1, 1, 2, 3, 3, 4] というソート済の配列に対して3以上の要素がどこから始まるかを知りたいときに使います。結果は 5 です。

C# で実装する

C# で実装するにあたり、イテレータではなくインデックスを返すようにします。

例えば lower_bound では「指定された要素以上の値が現れる最小のインデックス」を、upper_bound では「指定された要素より大きい値が現れる最小のインデックス」を返すことにします。

lower_bound

public static int LowerBound<T>(T[] a, T v)
{ 
    return LowerBound(a, v, Comparer<T>.Default);
}

public static int LowerBound<T>(T[] a, T v, Comparer<T> cmp)
{
    var l = 0;
    var r = a.Length - 1;
    while (l <= r)
    {
        var mid = l + (r - l) / 2;
        var res = cmp.Compare(a[mid], v);
        if (res == -1) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

実装は通常の二分探索とほぼ同じです。違いは一致する値のインデックスがわかってもそれが答えとは限らない点です。

例えば [1, 2, 2, 2, 2, 3, 4] というようなデータに対して2以上のデータを探す場合、2が見つかってもより小さいインデックスで2が存在するかもしれません。しかしそんなデータはないかもしれません。

比較関数を引数で渡して比較するようにしていますが、省略できるオーバーロードも用意しています。もっと便利に使いたい場合、拡張メソッドで定義するのが良いと思います。

実行例

var a = new[] { 1, 2, 2, 2, 4, 4, 4, 5, 6 };
for (int i = 0; i <= 7; i++)
{
    Console.WriteLine(LowerBound(a, i));
}
// 0
// 0
// 1
// 4
// 4
// 7
// 8
// 9

最大値よりも大きい要素を探すと配列外のインデックスを返します。

upper_bound

public static int UpperBound<T>(T[] a, T v)
{ 
    return UpperBound(a, v, Comparer<T>.Default);
}

public static int UpperBound<T>(T[] a, T v, Comparer<T> cmp)
{
    var l = 0;
    var r = a.Length - 1;
    while (l <= r)
    {
        var mid = l + (r - l) / 2;
        var res = cmp.Compare(a[mid], v);
        if (res <= 0) l = mid + 1;
        else r = mid - 1;
    }
    return l;
}

基本的な実装は lower_bound と同じですが、範囲を狭めるときの条件が微妙に違います。

実行例

var a = new[] { 1, 2, 2, 2, 4, 4, 4, 5, 6 };
for (int i = 0; i <= 7; i++)
{
    Console.WriteLine(UpperBound(a, i));
}
// 0
// 1
// 4
// 4
// 7
// 8
// 9
// 9

以上。