C#の配列やListを高速に検索する (BinarySearch)

配列やListクラスの要素を検索するメソッドといえば Find メソッドがあります。

この Find メソッドは先頭から１つ１つ要素を調べて探すというもので手軽ではあるものの速度はそれほど早くはありません。

要素数が多い配列を何度も検索するような場合、速度は無視できないものになります。

このようなケースでは BinarySearchメソッドを使いましょう。

BinarySearchは事前に検索条件で要素をソートしておく必要がある為、使い方には注意が必要がですがその分非常に高速に検索を行う事が出来ます。

配列の場合は Arrayクラスを利用します。Arrayクラスのメソッドは static になっており各メソッドの第1引数に配列を渡すようになっていますが、それ以外使い方はListクラスと同じです。

バイナリサーチとは

アルゴリズムを知らなくても使えれば良いわけですが、どのような仕組みで検索が行われているかを知っていれば Find と BinarySearch のどちらを使うべきかといった判断がしやすくなります。

特に BinarySearch には事前に検索条件で要素をソートしておく必要がありそこまで含めると Find の方が早いというケースもあり得ます。

バイナリサーチのアルゴリズム

バイナリサーチを日本語では二分探索と言ったりします。

その名の通り配列を２つに分けながら検索を進めていくアルゴリズムです。

100個の要素をもつ配列の場合を考えます
この配列は検索条件でソートされているものとします
配列の真ん中にある50番目の要素が条件に合うか検査してみます
50番目が目的の条件より小さかったなら50～100番目のどこかにある事が分かります（ソートされてるから）
50～100番目の真ん中である75番目の要素が条件に合うか検査してみます
75番目が目的の条件より大きかったなら50～75番目のどこかにある事が分かります
これを繰り返す事で条件と合致する要素を見つけ出します

先頭から１つ１つ条件を比較していくよりも比較回数が少なくて済むことが分かると思います。

検索メソッドの種類

検索のためのメソッドは以下のようにいくつか用意されています。

Listクラス

BinarySearch(T) ・・・既定の比較子を使用して検索します
BinarySearch(T, IComparer<T>) ・・・IComparerで比較して検索します
BinarySearch(int, int, T, IComparer<T>) ・・・IComparerで比較して指定の範囲を検索します

Arrayクラス

BinarySearch<T>(T[], T) ・・・既定の比較子を使用して検索します
BinarySearch<T>(T[], T, IComparer<T>) ・・・IComparerで比較して検索します
BinarySearch<T>(T[], int, int, T) ・・・既定の比較子を使用して指定の範囲を検索します
BinarySearch<T>(T[], int, int, T, IComparer<T>) ・・・IComparerで比較して指定の範囲を検索します

戻り値

結果が見つかった場合は要素のインデックス番号が返ります。

結果が見つからなかった場合はマイナス値が返りますが、戻り値のビットごとの補数(~演算子)をとる事で次に大きい要素のインデックス番号を知る事が出来ます。

IComparer<T>インターフェース

要素の比較には IComparer<T>インターフェースを利用します。

ソートも IComparer<T>インターフェースを引数とするメソッドが用意されています。

同じIComparer<T>でソートとバイナリサーチを実行しましょう。

    public interface IComparer<T>
    {
        int Compare(T x, T y);
    }

Compareメソッドを実装して比較条件を定義します。

Compareメソッドの戻り値は等しい場合は0、xの方が小さい場合はマイナス、xの方が大きい場合はプラスの値を返すようにします。

サンプルコード

以下の例では、バイナリサーチを使って要素の x が 3～5 のものを探し出しています。

    public class TestItem
    {
        public int x;
        public int y;
    }

    public class TestXComparer : IComparer<TestItem>
    {
        public int Compare(TestItem o1, TestItem o2)
        {
            if (o1.x < o2.x) return -1;
            if (o1.x > o2.x) return 1;
            return 0;
        }
    }

IComparer<T>インターフェースを実装したTestXComparerクラスは TestItem.x を比較対象しています。

private void Test()
{
    var list = new List<TestItem>();

    list.Add(new TestItem() { x = 5, y = 4 });
    list.Add(new TestItem() { x = 2, y = 1 });
    list.Add(new TestItem() { x = 4, y = 7 });
    list.Add(new TestItem() { x = 6, y = 3 });
    list.Add(new TestItem() { x = 9, y = 9 });
    list.Add(new TestItem() { x = 5, y = 6 });

    var comp = new TestXComparer();
    list.Sort(comp);

    var item = new TestItem();
    item.x = 3;
    item.y = 0;
    var index = list.BinarySearch(item, comp);
    if (0 > index)
        index = ~index;
    for (int i = index; i < list.Count; ++ i)
    {
        if (5 < list[i].x) break;
        System.Console.WriteLine("X=" + list[i].x + ",Y=" + list[i].y);
    }
}

まずリストを x でソートしています。(13行目)

検索条件を x = 3 とする TestItem を作成して検索します。(15～18行目)

リストに x が 3 の要素は存在しない為 index はマイナスとなりますが、補数をとると 3 より大きくなる最初の位置が取得できます。(19～20行目)