The following program implements binary search with the running time T of the Contains method proportional to lg(N), where N is the number of different integers in the array.

Note that the ratio lg(N)/lg(T) is approximately constant. It means that N as well as T is proportional to lg(N).

using System;
using System.Diagnostics;

namespace ConsoleTest
{
    class Program
    {
        private static Stopwatch stopwatch = new Stopwatch();
        private static Random rnd = new Random();
        private static int delayInMilisecond = 200;

        static void Main(string[] args)
        {
            double prev = RunTimeTrial(125);
            for (int N = 250; true; N += N)
            {
                double time = RunTimeTrial(N);
                Console.WriteLine("N: {0}   T: {1:F2}   lg(N)/lg(T): {2:F4}\n", N, time, Math.Log(N) / Math.Log(time));
                prev = time;
            }
        }

        static double RunTimeTrial(int N)
        {
            int[] a = new int[N];

            // Fill up an array with unique integers. The integers are already sorted.
            for (int i = 0; i < N; ++i)
                a[i] = i;

            stopwatch.Reset();
            stopwatch.Start();

            Contains(a, N + 1); // the worse case scenario: try to find an element which is not in the array

            return (stopwatch.ElapsedMilliseconds / 1000.0);
        }

        static bool Contains(int[] a, int key)
        {
            return (BinarySearch(a, key) != -1);
        }

        static int BinarySearch(int[] a, int key)
        {
            int low = 0;
            int high = a.Length - 1;

            while (low <= high)
            {
                System.Threading.Thread.Sleep(delayInMilisecond); // just for testing!

                int middle = low + (high - low) / 2;
                if (key < a[middle]) high = middle - 1;
                else if (key > a[middle]) low = middle + 1;
                else return middle;
            }

            return -1;
        }
    }
}

Sample output:

N: 500   T: 1.80   lg(N)/lg(T): 10.5530
N: 1000   T: 2.00   lg(N)/lg(T): 9.9514
N: 2000   T: 2.20   lg(N)/lg(T): 9.6236
N: 4000   T: 2.40   lg(N)/lg(T): 9.4559
N: 8000   T: 2.61   lg(N)/lg(T): 9.3830
N: 16000   T: 2.81   lg(N)/lg(T): 9.3759
N: 32000   T: 3.01   lg(N)/lg(T): 9.4195
N: 64000   T: 3.21   lg(N)/lg(T): 9.4940
N: 128000   T: 3.41   lg(N)/lg(T): 9.5956
N: 256000   T: 3.61   lg(N)/lg(T): 9.7049
N: 512000   T: 3.81   lg(N)/lg(T): 9.8279
N: 1024000   T: 4.01   lg(N)/lg(T): 9.9596
N: 2048000   T: 4.21   lg(N)/lg(T): 10.1081
N: 4096000   T: 4.41   lg(N)/lg(T): 10.2607
N: 8192000   T: 4.61   lg(N)/lg(T): 10.4209