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

namespace ConsoleApp1
{
    class BinarySearch
    {
        static public int? Search(int[] array, int key, int left, int right)
        {
            if ((array.Length == 0) || (key < array[0]) || (key > array[array.Length - 1]))
            {
                return null;
            }
            int mid = left + (right - left) / 2;

            if (left >= right)
            {
                return null;
            }

            if (array[mid] == key)
            {
                return mid;
            }

            else if (array[mid] > key)
            {
                return Search(array, key, left, mid);
            }
            else
            {
                return Search(array, key, mid + 1, right);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            int[] a = { 1, 3, 5, 7, 9 };
            Console.WriteLine("Шукаємо -1: {0}", BinarySearch.Search(a, -1, 0, a.Length));
            Console.WriteLine("Шукаємо  3: {0}", BinarySearch.Search(a, 3, 0, a.Length));
            Console.WriteLine("Шукаємо  6: {0}", BinarySearch.Search(a, 6, 0, a.Length));
            Console.WriteLine("Шукаємо  9: {0}", BinarySearch.Search(a, 9, 0, a.Length));
            Console.WriteLine("Шукаємо 20: {0}", BinarySearch.Search(a, 20, 0, a.Length));
        }
    }
}