自作探索プログラムで探索アルゴリズムを比較する。(コンソールアプリケーション / C#)

Search_Algo_Compare.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Search_Algo_Compare
{
    /// <summary>
    /// 自作探索プログラムで探索アルゴリズムを比較する。
    /// </summary>
    class Program
    {
        static int Calc_cnt = 0; // 試行回数を記録するための変数

        static void Main(string[] args)
        {
            // 入力待ち
            Console.Write("続行するには何かキーを押してください . . .");
            Console.Read();

            #region 配列準備

            var renge = 10000; // 配列の要素数
            var target = renge; // 探索する目的の数(今回は10000)
	    
            // 配列に順番に数を代入していき、要素をシャッフル(実験用)
            var deta = new List<int>();

            for (var i = 0; i < renge; ++i)
                deta.Add(i + 1);

            var n = deta.Count;
            var rnd = new Random();
            while (n > 1)
            {
                --n;
                var k = rnd.Next(n + 1);
                var tmp = deta[k];
                deta[k] = deta[n];
                deta[n] = tmp;
            }

            #endregion

            // 配列の内容を全て表示
            for (var i = 0; i < deta.Count; ++i)
                Console.Write(deta[i] + " ");
	    
            Console.WriteLine("\n\n目的の数 : " + target); // 目的の数を表示
	        
            // ここから線形探索
            Console.WriteLine("\n[線形探索 (Linear Search)]");
            Console.WriteLine(Linear_Search(deta, target) ? "存在する" : "存在しない");
            Console.WriteLine("試行回数 : " + Calc_cnt);

            Calc_cnt = 0; //試行回数のリセット

            // ここから二分探索
            Console.WriteLine("\n[二分探索 (Binary Search)]");
            Console.WriteLine(Binary_Search(deta, target) ? "存在する" : "存在しない");
            Console.WriteLine("試行回数 : " + Calc_cnt);

            // ここからC#が持っているバイナリサーチ
            Console.WriteLine("\n[C#のバイナリサーチ]");
            deta.Sort(); // リストを整列
            // 「BinarySearch」では、目的の数がどこに入っているのかをintで返す。
            var ret = deta.BinarySearch(target);
            Console.WriteLine(ret > 0 ? "存在する\n" : "存在しない\n");

        }

        /// <summary>
        /// 線形探索(リニアサーチ)
        /// </summary>
        /// <param name="deta">探索対象のリスト</param>
        /// <param name="value">探索目標</param>
        /// <returns>存在するか(True)、しないか(False)</returns>
        static bool Linear_Search(List<int> deta, int value)
        {
            for(var i = 0; i < deta.Count; ++i) // 要素数でループを回し、要素１つずつに対して比較を実行する。
            {
                ++Calc_cnt;
                if (deta[i] == value)
                {
                    return true;
                }
            }

            return false; // 最後まで見つからなかったら、False。
        }

        /// <summary>
        /// 二分探索(バイナリサーチ)
        /// </summary>
        /// <param name="deta">探索対象のリスト</param>
        /// <param name="value">探索目標</param>
        /// <returns>存在するか(True)、しないか(False)</returns>
        static bool Binary_Search(List<int> list, int value)
        {
            var tmp = new List<int>(list); // リストのコピー
            tmp.Sort(); // リストの整列

            int left = 0, mid = 0;
            var right = tmp.Last();
            while (right >= left)
            {
                ++Calc_cnt;
                mid = (right + left) / 2; //中央の数を計算
                if (tmp[mid] == value)
                    return true;
                else if (list[mid] < value)
                {
                    // 真ん中の数　< 探索目標　であれば、範囲を真ん中の数より大きい要素に絞り込む。
                    left = mid + 1;
                }
                else
                {
                    // 真ん中の数 > 探索目標　であれば、範囲を真ん中の数より小さい要素に絞り込む。
                    right = mid - 1;
                }
            }

            return false; // 最後まで見つからなかったら、False。
        }
    }
}