探索アルゴリズム

線形探索

線形探索
先頭から順番に探す値が見つかるまで探していく

配列を「直線的(リニア)に」探していくので「リニアサーチ」と呼ばれる。

単純でわかりやすいが、値をひとつひとつ調べていくためデータが大量になると時間がかかる探索方法になる。

線形探索

|

線形探索配下のように実現する

線形探索のAlgorithm

上図は楽しく学ぶ アルゴリズムとプログラミングの図鑑の紹介ページから引用

1. まず、「結果を入れる変数(find)」を用意して「-1」を入れる
2. 先頭から末尾まで比較をくり返す
3. 「探す値」と同じ値かどうかを比較する
4. もし同じ値なら、「結果を入れる変数(find)」を「その配列の番号」で上書きして、くり返しを終了する

単純なコードのため、実装例は省く

二分木探索

二分木探索(バイナリーサーチ)
ソート済みの配列において、検索する間隔を半分に分割しながらデータを探し出すアルゴリズム

ソート済みであることを利用して、徐々に値を見つけていく

二分木探索

1. 配列をソートする
2. 配列の中央にある要素を調べる
3. 探索を行う
   • 中央の要素が目的の値の場合:Trueを返す
   • 中央の要素が目的の値ではない場合
     • 目的のデータが中央の値より大きい場合:中央より後半の部分を調べる
     • 目的のデータが中央の値より小さい場合:中央より前半の部分を調べる
4. 2.に戻る

public class BinarySearch : Search
{
    public bool solver(int[] data_array, int target)
    {
        Array.Sort(data_array);

        int search_index = data_array.Length / 2;
        int search_length = search_index;
        do
        {
            if (target == data_array[search_index])
            {
                return true;
            }
            else if (search_length == 0)
            {
                return false;
            }
            else if (target > data_array[search_index])
            {
                search_length /= 2;
                if (search_length == 0)
                    search_index++;
                else
                    search_index += search_length;
            }
            else
            {
                search_length /= 2;
                if (search_length == 0)
                    search_index--;
                else
                    search_index -= search_length;
            }
        } while (true);
    }
}