using System;

using System.Linq;

using System.Diagnostics;

​

public static class Answer

{

    public static bool Exists( int[] ints, int k )

    {

        var lower = 0;

        var upper = ints.Length - 1;

​

        if ( k < ints[lower] || k > ints[upper] ) return false;

        if ( k == ints[lower] ) return true;

        if ( k == ints[upper] ) return true;

​

        do

        {

            var middle = lower + ( upper - lower ) / 2;

​

            if ( ints[middle] == k ) return true;

            if ( lower == upper ) return false;

​

            if ( k < ints[middle] )

                upper = Math.Max( lower, middle - 1 );

            else

                lower = Math.Min( upper, middle + 1 );

        } while ( true );

    }

    public static bool Exists2(int[] ints, int k)

    {

        var i = 0;

        var hasValue = false;

​

        while(i < ints.Length && !hasValue)

        {

            hasValue = ints[i] == k;

            ++i;

        }

​

        return hasValue;

    }

}

public class Program

{

    public static void Main()

    {

        var count = 500000;

        var numbers = Enumerable.Range( 1, count ).ToArray();

        Stopwatch sw;

        bool result;

        Console.WriteLine("Lets run the test");

        // just to warm up

        result = Answer.Exists( numbers, count-1 );

        result = Answer.Exists2( numbers, count-1 );

        // now to the facts

        sw = Stopwatch.StartNew();

        result = Answer.Exists( numbers, count-1 );

        sw.Stop();      

        Console.WriteLine( string.Format( "{0} ({1} ticks elapsed)", result, sw.Elapsed.Ticks ) );

        sw = Stopwatch.StartNew();

        result = Answer.Exists2( numbers, count-1 );

        sw.Stop();      

        Console.WriteLine( string.Format( "{0} ({1} ticks elapsed)", result, sw.Elapsed.Ticks ) );

​

    }

}