namespace binarysearch
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int[] A = new int[8] { 1, 4, 10, 12, 25, 34, 39, 45 };
            Console.WriteLine("Please give the key k: ");
            int k = int.Parse(Console.ReadLine());
            int s = BinarySearch(A, 0, 7, k);

            if (s == -1)
                Console.WriteLine("The search key {0} is not in array A.", k);
            else
                Console.WriteLine("The search key {0} is the {1}th element of array A.", k, s + 1);
            Console.ReadLine();
        }

        public static int BinarySearch(int[] A, int p, int r, int k)
        {
            if (p == r)
                if (A[p] == k)
                    return p;
                else
                    return -1;
            else
            {
                int q = (p + r) / 2;
                if (A[q] == k)
                    return q;
                else if (A[q] < k)
                    return BinarySearch(A, q + 1, r, k);
                else
                    return BinarySearch(A, p, q, k);
            }
        }
    }
}