二分探索とは
二分探索(バイナリサーチ)とはソート済みの配列に対する探索アルゴリズムの一つです。
ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
先頭から順番に探していく方法(線形探索)ではデータがn個ある場合はo(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"); } }
5 array[2] : 5
8
Not Found
さいごに
ただしソートされている配列でないと利用できないことに注意してください。
アルゴリズムの基本となるものなので、是非習得しておくと良いと思います。
ではまた。