using System;
using System.Collections.Generic;
using System.Linq;

namespace Binary_Search
{
    class Program
    {
        static int NumberToFind;
        static void Main(string[] args)
        {
            var NumsList = new List<int>();
            bool valid_input = false;
            
            for (int i = 0; i <= 10001; i++)
            {
                NumsList.Add(i);
            }
            
            while (valid_input == false)
            {
                Console.WriteLine("Choose a number 1-10,000");
                NumberToFind = Convert.ToInt32(Console.ReadLine()); // get user to give the number they want to find

                if (NumberToFind > 10000)
                {
                    Console.Clear();
                    Console.WriteLine("{0} is not in the list", NumberToFind);
                    Console.WriteLine("Hit any key to continue");
                    Console.ReadKey();
                    Console.Clear();

                    valid_input = false;
                }

                else
                {
                    valid_input = true;
                }
            }

            Binary_Search(NumsList, NumberToFind, NumsList.Min(), NumsList.Max(), 0); // call binary_search

            Console.ReadKey();
        }

        static int Binary_Search(List<int> list, int Value, int Min, int Max, int Steps)
        {
            int Mid_Point = (Min + Max) / 2; // get index of the middle of the list

            /*
             * looking at this list
             * 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
             */

            if (list[Mid_Point] < Value) // middle value is less than the value inputed
            {
                Binary_Search(list, Value, Mid_Point + 1, Max, Steps + 1);

                /*
                 * looking at this list
                 * 11 12 13 14 15 16 17 18 19 20
                 */

                return 0;
            }

            else if (list[Mid_Point] > Value) // middle value is more than the value inputed
            {
                Binary_Search(list, Value, Min, Mid_Point - 1, Steps + 1);

                /*
                 * 
                 * 10 11 12 13 14 15 16 17 18 19 20
                 */

                return 0;
            }

            else
            {
                Console.WriteLine("{0} found in {1} steps", Value, Steps);
                return Mid_Point;
            }
        }
    }
}