// Implement binary search: the function takes strictly ascending integer array and returns

// an index of the element that is equal to given value or -1 if there is no such element.

using System;

​

public class Solution

{

    public static int Find(int[] a, int key)

    {   

        return Find(a, 0, a.Length, key);

    }

    // a is sorted in ascending order

    // 0 <= start <= end <= a.Length

    // key does not occur before a[start] or after a[end-1]

    // Completion: each nested call excludes at least one element from search range (a[mid])

    // Complexity: the range in nested call is decreased approximately twice, hence we have log N depth and time.

    public static int Find(int[] a, int start, int end, int key)

    {

        if(start == end)

            return -1;

        int mid = (start + end) / 2;

        // start <= mid <= end

​

        if(a[mid] == key)

            return mid;

​

        if(a[mid] < key)    // key cannot be in a[mid] and before

            return Find(a, mid + 1, end, key);

        else    // key cannot be in a[mid] and after

            return Find(a, start, mid, key);

    }

    public static void Main(string[] args)

    {

        int[] a = {1, 4, 6, 7, 8, 13, 15, 16};

        foreach(int key in a)

        {

            Test(a, key - 1);

            Test(a, key);

            Test(a, key + 1);

        }

    }

​

    public static void Test(int[] a, int key)

    {

        int index = Find(a, key);

        if(index >= 0)

            Console.WriteLine("{0} is present at index {1}", key, index);

        else

            Console.WriteLine("{0} is not found", key);

    }

}

​