using System;

public class Program

{

    public static void Main()

    {

        Console.Write("【Binary Search】\n請輸入欲尋找數字：");

        int target = int.Parse(Console.ReadLine());

        int seq_len=100;

        int[] sequence = new int[seq_len];

        Random rand = new Random();

        sequence[0] = rand.Next(1,101);

        for (int i=1;i<100;i++)

        {

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

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

            {

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

                    {

                        sequence[i] = rand.Next(1,101); //重新定義

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

                    }

            }

        }

        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;

        while(low<=high)

        {

            midpoint=(high+low)/2;

            if (sequence[midpoint]==target)

            {

                Console.WriteLine("Found in index "+midpoint);

                break;

            }

            else if (sequence[midpoint]>target)

                high = midpoint-1;

            else

                low = midpoint+1;

        }

    }

}