【C#】二分探索の実装（範囲インデクス指定実装）

ヽ｜∵｜ゝ(Fantom) の開発blog？ホーム » C# »【C#】二分探索の実装（範囲インデクス指定実装）

【C#】二分探索の実装（範囲インデクス指定実装）

2019/10/11 Fri [edit]

　ただの実装用メモ。元々標準ライブラリで BinarySearch は実装されているので(配列も同様)、利用するだけなら、自分で実装する必要はない。ちょっと改造して、検索を高速化したいときにアルゴリズムだけ利用することもあるので（Java の標準ライブラリはすぐ実装見れるが、C# の標準ライブラリってメタデータだけだったりするので）、確認用に書いておいた。

●インデクスで範囲指定の二分探索の実装

using System;
using System.Collections.Generic;

/// <summary>
/// インデクスで範囲指定の二分探索
/// 2019/10/11 Fantom
/// http://fantom1x.blog130.fc2.com/blog-entry-338.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>0 以上のとき見つかったインデクス / 0 より小さいとき ~index (ビット反転)で挿入位置になる</returns>
public static int BinarySearch<T>(this List<T> list, int start, int end, T value, IComparer<T> comparer)
{
    int low = start;
    int high = end - 1;
    int mid;
    while (low <= high)
    {
        mid = ((high - low) >> 1) + low;
        if (comparer.Compare(list[mid], value) < 0)
        {
            low = mid + 1;
        }
        else if (comparer.Compare(list[mid], value) > 0)
        {
            high = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -(low + 1);
}

//引数省略のオーバーロード
public static int BinarySearch<T>(this List<T> list, int start, int end, T value)
{
    return BinarySearch(list, start, end, value, Comparer<T>.Default);
}

　実際には以前に書いた、LowerBound, UpperBound（配列で実装してるが、List でも同じ）と BinarySearch を使い分けると便利だったりする。大きな違いは検索結果のインデクスの値で、例えば BinarySearch では同値が並んでいるとどのインデクスになるかは不定だが、LowerBound を使うと同値の最初のインデクス、UpperBound を使うと同値の最後の次のインデクスとなる（「検索する値の個数を求める」の例がわかり易いと思う）。

　私の場合、一部のプロパティを二分探索で検索するために（例えば常にインクリメントする ID 番号など）、上記の実装を少し改造して使うことも多い。大量にデータが増えたとき、二分探索はその効果を発揮する（よく FindIndex や FirstOrDefault で実装されている場合も多いが、逐次検索なので大量のデータには向かない）。LowerBound, UpperBound と共に使えば、かなりの高速化ができるので、色々やってみると良いだろう。