// Write a function that accepts an integer number and array of strictly ascending

// integers and returns true if this array contains given number and false otherwise.

​

using System;

public class Program

{

    public static void Main(string[] args)

    {

        int[] a = {1, 2, 3, 4, 5, 6, 7, 13, 22, 39, 53, 71};

        foreach(int test in new int[] {0, 1, 2, 9, 5, 13, 79})

        {

            Console.WriteLine("contains({0}) = {1}", test, contains( test, a));

        }

    }

    public static bool contains(int what, int[] where)

    {

        if(where.Length == 0)

            return false;   

        // where.Length > 0

        int l = 0;

        int r = where.Length;

        // invariant: what can occur only within where[l..r-1] and l <= r + 1

        while(l != r - 1)

        {

            // r - l >= 2 => (l - r) / 2 > 0

            int m = (l + r) / 2;

            // note: m - l = (l + r) / 2 - l = (l + r - 2l) / 2 = (r - l) / 2 > 0 => l < m

            // note: m - r = (l + r) / 2 - r = (l + r - 2r) / 2 = (l - r) / 2 < 0 => m < r

            // l < m < r

            if (where[m] <= what)

                l = m;

            else  // what < where[m]

                r = m;

        }

        // what can occur only within where[l..r-1] and l = r - 1 => what can be only at where[l]

        return where[l]==what;

        // (r - l) is being decreased twice on each iteration, hence

        // Time = O(log n)

    }

}