using System;
 
namespace BinarySearch
{
    class Program
    {
        static void Main(string[] args)
        {
 
            int[] a = new int[] { 2, 4, 6, 8, 9 };
            Console.WriteLine(BinarySearchIterative(a, 9));
            Console.WriteLine(BinarySearchRecursive(a, 9, 0, a.Length));
        }
 
        private static int BinarySearchIterative(int[] a, int val){
            int low = 0;
            int high = a.Length;
            while (low <= high)
            {
                int mid = (low + high) / 2;
                if (a[mid] > val)
                    high = mid-1;
                else if (a[mid] < val)
                    low = mid+1;
                else
                    return mid;
            }
            return -1;
        }
 
        private static int BinarySearchRecursive(int[] a, int val, int low, int high)
        {
            if (high < low)
                return -1;
            int mid = (low + high) / 2;
            if (a[mid] > val)
                return BinarySearchRecursive(a, val, low, mid - 1);
            else if (a[mid] < val)
                return BinarySearchRecursive(a, val, mid + 1, high);
            else
                return mid;
        }
    }
}