[C#][VB] 二分探索(バイナリサーチ)の実装

二分探索(バイナリサーチ)とは

二分探索 – Wikipedia

二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

要素数nの配列に対して線形探索する場合(先頭から順番に探す方法)は、時間計算量が O(n) となります。それに対して二分探索(バイナリサーチ)は O(log n) と高速に動作します。ただしソート済の配列に対してしか動作します。

• List.BinarySearch Method (System.Collections.Generic) | Microsoft Docs
• Array.BinarySearch Method (System) | Microsoft Docs

上記URLのとおり .NET(C#, VB.NET) にはバイナリサーチが用意されていますが、自前で実装で配列を対象にした処理を実装してみます。おそらく Array.BinarySearch() と同じような動作ができるようにします。。

アルゴリズム

処理の流れは結構単純で、配列の真ん中の要素xを比較対象として、x より大きい場合は真ん中より後ろ側、小さい場合は手前側にあるというのがわかります。見つかる可能性のある範囲が狭まるので、あとはこれを繰り返すと対象の要素が見つかるという寸法です。

手順は以下のような感じです。

1. 配列全体を探索範囲とする
2. 探索範囲内にデータが無ければ探索を終了
3. 探索範囲のデータから中央値(対象の真ん中の要素)を取り出す
4. 取り出したデータが目的のデータかどうか比較
5. 目的のデータに一致すれば探索完了
6. 目的のデータより中央値が大きい場合、探索範囲の最大値を中央値まで狭めて 2. に戻る
7. 目的のデータより中央値が小さい場合、探索範囲の最小値を中央値まで狭めて 2. に戻る

実装(C#)

static int BinarySearch<T>(T[] array, T target) where T : IComparable<T>
{
    // 探索範囲のインデックス
    var min = 0;
    var max = array.Length - 1;

    while (min <= max) // 範囲内にある限り探し続ける
    {
        var mid = min + (max - min) / 2;
        switch (target.CompareTo(array[mid]))
        {
            case 1:  // 中央値より大きい場合
                min = mid + 1;
                break;
            case -1: // 中央値より小さい場合
                max = mid - 1;
                break;
            case 0:
                return mid;
        }
    }
    return -1; // 見つからなかった
}

探索範囲の開始終了のインデックスとして min, max を保持します。これが範囲外になりまで処理を続けます。

mid は探索範囲のちょうど真ん中のインデックスです。この要素を探索対象の要素を比較して範囲の前半か後半どちらにあるかがわかります。

var mid = (min + max) / 2; として計算すると、場合によってオーバーフローする可能性があるので注意しましょう。

前半にある場合は max を mid-1 にして、真ん中の要素より手前を探索範囲に再設定しています。後半にある場合は min を mid+1 にして、真ん中の要素より後ろを探索範囲に再設定しています。

中央値が探索対象の要素そのものであればそのインデックスを返します。

要素が見つからない場合は max と min の範囲が逆転して不正な状態になります。この時は見つからなかったと判定できるので処理を抜けて -1 を返すということになります。

動作確認

線形探索と比較して動作を確認してみます。ソート済の連番の配列(2億個)から要素を探してみます。末尾の要素(最悪のケースの比較)です。

var a = Enumerable.Range(1, 200000000).ToArray();
var target = 200000000;

{
    var sw = new Stopwatch();
    sw.Start();
    var index = LinearSearch(a, target);
    sw.Stop();

    // 線形探索: 00:00:00.7592970, index: 199999999
    Console.WriteLine($"線形探索: {TimeSpan.FromTicks(sw.ElapsedTicks)}, index: {index}");
}
{
    var sw = new Stopwatch();
    sw.Start();
    var index = BinarySearch(a, target);
    sw.Stop();

    // 二分探索: 00:00:00.0002043, index: 199999999
    Console.WriteLine($"二分探索: {TimeSpan.FromTicks(sw.ElapsedTicks)}, index: {index}");
}

線形探索に比べて圧倒的に早く動作が完了していることがわかります。

線形探索は単純にループして先頭から探す感じです。一応コードを載せておきます。

static int LinearSearch<T>(T[] array, T target) where T : IComparable<T>
{
    for (int i = 0; i < array.Length; i++)
    {
        if (array[i].CompareTo(target) == 0)
        {
            return i;
        }
    }
    return -1;
}

実装(VB.NET)

Function BinarySearch(Of T As IComparable)(array As T(), target As T) As Integer
    Dim min As Integer = 0
    Dim max As Integer = array.Length - 1

    While min <= max
        Dim mid As Integer = min + (max - min) / 2
        Select Case target.CompareTo(array(mid))
            Case 1
                min = mid + 1
            Case -1
                max = mid - 1
            Case 0
                Return mid
        End Select
    End While
    Return -1
End Function

参考URL

• List.BinarySearch Method (System.Collections.Generic) | Microsoft Docs
• 二分探索 – Wikipedia
• 二分探索法（バイナリサーチ） – Algoful