using System;

public class Program

{

    public static void Main()

    {

        int target , seq_len = 5000 ;

        Console.Write("請輸入想找的數字：");//使用者將想找的數值輸入。

        target = int.Parse(Console.ReadLine());//讀取數值。

        int[] sequence = new int[seq_len];//給一個陣列。

        Random rand = new Random();

        sequence[0] = rand.Next(1,5001);//將1~5000的數值打亂。

        for (int i=1;i<5000;i++)//做迴圈，將1~5000的數值放到至陣列的5000個格子裡。

        {

            sequence[i] = rand.Next(1,5001);

            for (int j=0;j<i;j++)

            {

                if (sequence[j] == sequence[i]) //檢查亂數是否有重複。

                    {

                        sequence[i] = rand.Next(1,5001); //若有重複就會重新定義。

                        j=0; //如有重複則j變成0，再檢查

                    }

            }

        }

        //Linear

        int k=0;

        for (int i=0;i<sequence.Length;i++)

        {

            k = k + 1;

            if (sequence[i]==target)

                Console.WriteLine("【Linear Search】 當值為{0}時，共搜尋了{1}次後找到。",target,k);

        }

        //Binary

        for (int i=0; i<=seq_len; i++)

        {

            for (int j=0; j<seq_len-1; j++)

            {

                if (sequence[j]>sequence[j+1])

                {

                    int temp=sequence[j];

                    sequence[j]=sequence[j+1];

                    sequence[j+1]=temp;

                }

            }

        }

        int low=0, high=seq_len-1, midpoint=0;

        int y=0;

        while(low<=high)

        {

            midpoint=(high+low)/2;

            if (sequence[midpoint]==target)

            {

                y = y + 1;

                Console.WriteLine("【Binary Search】 當值為{0}時，共搜尋了{1}次後找到。",target,y);

                break;

            }

            else if (sequence[midpoint]>target)

            {

                y++;

                high = midpoint-1;

            }

            else

            {

                y++;

                low = midpoint+1;

            }

        }

        if (k<y)

        {

            Console.WriteLine("Libear Search比Binary Search快");

        }

        else if (k>y)

        {

            Console.WriteLine("Binary Search比Libear Search快");

        }

        else

        {

            Console.WriteLine("Libear Search跟Binary Search的搜尋速度一樣");

        }

    }

}