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

namespace ConsoleApplication1
{
    class Program
    {
        static void extreme_to_middle(int[] a, int n)
        {
            if (n == 1)
            {
                Console.Write(a[0]);
                return;
            }
            Console.Write(a[0] + ", " + a[n - 1] + " ,");
            int[] b = new int[a.Length-1];
            for(int i = 1;i < a.Length;i++)
                b[i-1] = a[i];
            extreme_to_middle(b, n - 2);
            return;
        }
        static int bcd(int a, int b)
        {
            if (b == 0) return a;
            return bcd(b, a % b);
        }
        static void rec_sort(int[] arr,int n)
        {
            if (n+1 >= arr.Length) return;
            if (arr[n] > arr[n + 1])
            {
                int tmp = arr[n + 1];
                arr[n + 1] = arr[n];
                arr[n] = tmp;
                rec_sort(arr, n-1);
            }
            else
                rec_sort(arr, n+1);
        }
        static void print(int[] arr,int n)
        {
            if (arr.Length == n + 1) Console.Write(arr[n]);
            else
            {
                Console.Write(arr[n] + ", ");
                print(arr, n + 1);
            }
        }
        static bool find(int[] arr, int num, int left, int right)
        //          left = 0;
        //          right = arr.Length;
        {
            if (arr[right] < num || arr[left] > num || left == right) return false;
            int mid = (left+right)/2+1;
            if (arr[mid] < num)
            {
                if (mid == left) return false;
                left = mid;
            }
            else if (arr[mid] > num)
            {
                if (mid == right) return false;
                right = mid;
            }
            else
                return true;
            return find(arr, num, left, right);
        }
        static void Main(string[] args)
        {
            int[] a = new int[10];
            a[0] = 1;
            a[1] = 9;
            a[2] = 8;
            a[3] = 3;
            a[4] = 2;
            a[5] = 7;
            a[6] = 6;
            a[7] = 4;
            a[8] = 7;
            a[9] = 7;
            print(a,0);
            Console.WriteLine();
            rec_sort(a,0);
            print(a,0);
            Console.WriteLine();
            int n = 5;
            Console.WriteLine("Does " + n + " exist in the array? " + find(a,n,0,a.Length-1));
            Console.ReadLine();
        }
    }
}