【C#】 LowerBound, UpperBound （二分探索）

2017/08/04 Fri [edit]

　私は時折、頭の体操代わりにプロコン問題を解いたりしているのだが、使う言語はその時々で変えてるので、関数によっては無いと不便に思うものがある。LowerBound, UpperBound はその代表例かな。ものによっては BinarySearch でも同じ結果を得られるものもあるが、やはりあった方が良いので改めて書いておくことにした。内容的には Java や Ruby 版と同じ。使い所を覚えれば、簡潔かつ高速に処理できるので、二分探索系のアルゴリズムは知っておいても損はないだろう。

■C#版 LowerBound, UpperBound
■いくつかの値の範囲で何番目の要素かを求める
■検索する値の個数を求める

■C# 版 LowerBound, UpperBound

using System;
using System.Collections.Generic;

/// <summary>
/// 指定した値以上の先頭のインデクスを返す (二分探索)
/// 2017/08/04 Fantom
/// http://fantom1x.blog130.fc2.com//blog-entry-256.html
/// </summary>
/// <typeparam name="T">比較する値の型</typeparam>
/// <param name="arr">対象の配列（※ソート済みであること）</param>
/// <param name="start">開始インデクス [inclusive]</param>
/// <param name="end">終了インデクス [exclusive]</param>
/// <param name="value">検索する値</param>
/// <param name="comparer">比較関数(インターフェイス)</param>
/// <returns>指定した値以上の先頭のインデクス</returns>
public static int LowerBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
    int low = start;
    int high = end;
    int mid;
    while (low < high)
    {
        mid = ((high - low) >> 1) + low;
        if (comparer.Compare(arr[mid], value) < 0)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

//引数省略のオーバーロード
public static int LowerBound<T>(T[] arr, T value) where T : IComparable
{
    return LowerBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}

/// <summary>
/// 指定した値より大きい先頭のインデクスを返す (二分探索)
/// 2017/08/04 Fantom
/// http://fantom1x.blog130.fc2.com//blog-entry-256.html
/// </summary>
/// <typeparam name="T">比較する値の型</typeparam>
/// <param name="arr">対象の配列（※ソート済みであること）</param>
/// <param name="start">開始インデクス [inclusive]</param>
/// <param name="end">終了インデクス [exclusive]</param>
/// <param name="value">検索する値</param>
/// <param name="comparer">比較関数(インターフェイス)</param>
/// <returns>指定した値より大きい先頭のインデクス</returns>
public static int UpperBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
    int low = start;
    int high = end;
    int mid;
    while (low < high)
    {
        mid = ((high - low) >> 1) + low;
        if (comparer.Compare(arr[mid], value) <= 0)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

//引数省略のオーバーロード
public static int UpperBound<T>(T[] arr, T value)
{
    return UpperBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}

　ついでに引数省略のオーバーロードも書いてあるが、実際にはもう何パターンかあった方が便利かも知れない（全要素＋IComparer指定 / 範囲指定＋IComparer省略など）。もし予め検索の範囲が絞りこめるなら、更に高速に処理できるので範囲指定はオススメだ。プロコン問題やリアルタイム処理が必要な高負荷アプリケーションなどでは積極的に使っていこう。

　ちなみに返ってくるインデクスは LowerBound は「指定した値以上の先頭のインデクス」で、UpperBound は「指定した値より大きい先頭のインデクス」になる。BinarySearch の場合は、値が見つかった場合はそのインデクスが返り、見つからないとき負の値となり、ビット反転することで「指定した値より大きい先頭のインデクス」が返る（つまり毎回正負を調べる必要がある）。完全一致の有無を調べるには BinarySearch の方が便利だが、一番近い値のインデクス見つけるなら LowerBound や UpperBound の方が便利だ。使い分けると良いだろう。

　以降は簡単な使用例なので、既に知っているなら読み飛ばしても良いだろう。

■いくつかの値の範囲で何番目の要素かを求める

　例えば以下のような表があり、「ある風速に対して風力を求める」問題があったとする。実際にこの問題は AtCoder の練習問題の一部を抜粋したものだが、色々な人の解答例を見ていると（AtCoder や yukicoder などは他の人の解答を見れるので勉強になる）、逐次検索または if 文で頭から値を比較しているものが圧倒的に多い。しかしこの表のように単調増加なものなら、二分検索が使えると考えて良い。この場合は UpperBound を使うと簡単だ。

風力	風速
風力0	0.0m⁄s 以上 0.2m⁄s 以下
風力1	0.3m⁄s 以上 1.5m⁄s 以下
風力2	1.6m⁄s 以上 3.3m⁄s 以下
風力3	3.4m⁄s 以上 5.4m⁄s 以下
風力4	5.5m⁄s 以上 7.9m⁄s 以下
風力5	8.0m⁄s 以上 10.7m⁄s 以下
風力6	10.8m⁄s 以上 13.8m⁄s 以下
風力7	13.9m⁄s 以上 17.1m⁄s 以下
風力8	17.2m⁄s 以上 20.7m⁄s 以下
風力9	20.8m⁄s 以上 24.4m⁄s 以下
風力10	24.5m⁄s 以上 28.4m⁄s 以下
風力11	28.5m⁄s 以上 32.6m⁄s 以下
風力12	32.7m⁄s 以上

●UpperBound を使っての解答例

//※・・・関数などは略・・・

//表の各要素の開始の風速を配列にしたもの
double[] WindPower = {
    0.0, 0.3, 1.6, 3.4, 5.5, 8.0, 10.8, 13.9, 17.2, 20.8, 24.5, 28.5, 32.7
};

double ms = 15.3; //※与えられた風速とする(m/s)
int wp = UpperBound(WindPower, ms) - 1;
Console.WriteLine("風速" + wp);

風速7

　実はこの問題の場合は BinarySearch でも事足りる。しかし BinarySearch の場合、値が見つかった時と見つからなかったときで処理を分岐する必要があり、冗長となることも多い。

●Array.BinarySearchを使っての解答例

//※・・・関数などは略・・・

//表の各要素の開始の風速を配列にしたもの
double[] WindPower = {
    0.0, 0.3, 1.6, 3.4, 5.5, 8.0, 10.8, 13.9, 17.2, 20.8, 24.5, 28.5, 32.7
};

double ms = 15.3; //※与えられた風速とする(m/s)
int wp = Array.BinarySearch(WindPower, ms);
Console.WriteLine("風速" + (wp < 0 ? ~wp - 1 : wp)); //見つからなかったときビット反転（~）するとUpperBoundと同じになる

風速7

　実際にはこの問題くらいの要素数なら逐次検索でも構わないのだが、要素数が何千とあったり、60fpsで動作するゲームなどでフレーム毎で使用する必要などあった場合、検索回数を大幅に減らせるので効果はてきめんとなる。

■検索する値の個数を求める

　次によくあるパターンだが、ある数が連続して並んでいるとき、その範囲や個数を調べる方法などもある。例えば以下のような表があったとき、「2～4 の値を持つインデクスの範囲とその要素数を求めたい」としよう。一番初めに思い浮かぶアルゴリズムは先頭から検索していき、2 が出てきた所で開始インデクスを記録、4 より上の値が出てきた所で終了インデクスを記録するといった感じだろうか。開始と終了の差を取ればその個数もわかる。しかし、ここでは LowerBound, UpperBound を使ってみよう。

Index	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	[11]	[12]
Value	0	0	1	1	1	2	2	3	4	4	4	5	5

//※・・・関数などは略・・・

int[] arr = {0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5}; //表
int low  = 2; //検索する最小値
int high = 4; //検索する最大値
int from = LowerBound(arr, low); //検索する最小値で最初のインデクス
int to = UpperBound(arr, high);  //検索する最大値を超えた最初のインデクス
Console.WriteLine("from = " + from + ", to = " + to + ", count = " + (to - from));

from = 5, to = 11, count = 6

　この例も要素数が少ない場合は逐次検索でもそれほど大差ないが、何千・何万という要素数でなら、圧倒的な速さとなる。

　私の見たところ、実際の開発現場でのコードでも逐次検索は多用されている感じがあるので、データが単調増加ないし単調減少なら二分探索を取り入れると良いと思う。確実に高速化できるし、もしデータを順に並べて良いものなら、予めリアルタイムにソート済みデータを作っていくアルゴリズムを組んでおけば、何かと便利なことが多い（Ruby 版だが「ソート済み配列を作る」方法もある[※C# なら List にすると良い]）。

　この辺りは慣れだと思うが、常に検索回数を減らせるような工夫を忘れないようにすれば、paiza や CodeIQ などの上級者問題（A, S ランク）も解けるようになる（タイムアウトしなくなる）。挑戦してみると良いだろう。