【C#】二分探索(バイナリサーチ)をする

はじめに

今回は二分探索をしてみようという記事になります！

はじめに
二分探索とは
コード
さいごに

二分探索とは

二分探索(バイナリサーチ)とはソート済みの配列に対する探索アルゴリズムの一つです。

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

二分探索 - Wikipedia

先頭から順番に探していく方法(線形探索)ではデータがn個ある場合はo(n)かかってしまいますが、二分探索なら $o(log_2(n))$ で済みます。

コード

/// <summary>
/// 二分探索
/// </summary>
/// <param name="array">ソートされた配列</param>
/// <param name="target">探す数</param>
/// <param name="min">探索範囲の最初のインデックス</param>
/// <param name="max">探索範囲の最後のインデックス</param>
/// <returns>探す数のインデックス</returns>
public static int BinarySearch<T>(T[] array, T target, int min, int max) where T : IComparable<T>
{
    if (max < min) return -1;           // 見つからなかった

    int mid = min + (max - min) / 2;    // 探索範囲の真ん中のインデックス

    if (array[mid].CompareTo(target) > 0) return BinarySearch(array, target, min, mid - 1);
    else if (array[mid].CompareTo(target) < 0) return BinarySearch(array, target, mid + 1, max);

    return mid;
}

これを使ってみるとこんな感じ。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        // 探す値を入力
        var target = int.Parse(Console.ReadLine());

        // 奇数を10個
        int[] array = Enumerable.Range(1, 10).Select(t => 2 * t - 1).ToArray();

        // 二分探索
        var index = BinarySearch<int>(array, target, 0, array.Length - 1);

        if (index != -1) Console.WriteLine($"array[{index}] : {array[index]}");
        else Console.WriteLine("Not Found");
    }
}