Find a value in a sorted matrix

SortedMatrix.cs

using System;
using System.Diagnostics;
using System.Collections.Generic;

namespace ConsoleApplication4
{
    /// <summary>
    /// 
    /// </summary>
    /// <remarks>
    /// Some test result for different N:
    /// 
    /// N = 1000:
    /// Timer1: 1574
    /// Timer2: 7429
    /// 
    /// N = 10000:
    /// Timer1: 7307
    /// Timer2: 7867
    /// 
    /// Note that FindInSortedMatrix takes O(N) to run (on average case)
    /// Finder.Find() takes O((logN)^2) to run (on average case)
    /// 
    /// When N gets large, (logN)^2 < N
    /// 
    /// See: http://www.wolframalpha.com/input/?i=%28log%28x%29%29%5E2+%3C+x
    /// </remarks>
    class Program
    {
        static HashSet<int> ValueNotToBeIncluded = new HashSet<int> { -999, 1, 999 };

        static void Main(String[] args)
        {
            Main_Profiling_Random(args);
        }

        static void Main_Profiling_Random(string[] args)
        {
            int N = 1000;
            var A = new int[N, N];
            GenerateRandomSortedArray(A);
            var timer1 = new Stopwatch();
            var timer2 = new Stopwatch();

            foreach (Tuple<int,int> pos in new Tuple<int, int>[] { 
                        new Tuple<int,int>( 0, 0 ),
                        new Tuple<int,int>( 0, N/2),
                        new Tuple<int,int>(0, N-1),
                        new Tuple<int,int>(N/2, 0),
                        new Tuple<int,int>(N-1, 0),
                        new Tuple<int,int>(N/2, N/2),
                        new Tuple<int,int>(N/2, N-1),
                        new Tuple<int,int>(N-1, N/2),
                        new Tuple<int,int>(N-1, N-1)
            })
            {
                int x = A[pos.Item1, pos.Item2];
                
                Console.WriteLine("Running 1st algo");
                timer1.Start();
                FindInSortedMatrix(A, x);
                timer1.Stop();

                var finder = new Finder(A, x);
                Console.WriteLine("Running 2nd algo");
                timer2.Start();
                finder.Find();
                timer2.Stop();
            }
            /*
            foreach (int findWhat in ValueNotToBeIncluded)
            {
                timer1.Start();
                FindInSortedMatrix(A, findWhat);
                timer1.Stop();

                timer2.Start();
                (new Finder(A, findWhat)).Find();
                timer2.Stop();
            }*/

            Console.WriteLine("Timer1: {0}", timer1.ElapsedTicks);
            Console.WriteLine("Timer2: {0}", timer2.ElapsedTicks);
            Console.Read();
        }

        static void GenerateRandomSortedArray(int[,] A)
        {
            Console.WriteLine("Generating sorted array...");
            int M = A.GetLength(0);
            int N = A.GetLength(1);
            for (int r = 0; r < M; r++)
            {
                for (int c = 0; c < N; c++)
                {
                    int base_;
                    if (r == 0) base_ = c == 0 ? int.MinValue : A[0, c - 1];
                    else if (c == 0) base_ = A[r - 1, 0];
                    else base_ = Math.Max(A[r - 1, c], A[r, c - 1]);
                    int shift;
                    do
                    {
                        shift = (new Random()).Next(0, 10);
                        A[r, c] = base_ + shift;
                    } while (ValueNotToBeIncluded.Contains(base_ + shift));
                }
            }

            /*
            // ---------- test if it's valid ------------------
            // test that each row is sorted
            for (int r = 0; r < M; r++)
            {
                for (int c = 1; c < N; c++)
                {
                    Debug.Assert(A[r, c - 1] <= A[r, c]);
                }
            }

            // test that each column is sorted
            for (int c = 0; c < N; c++)
            {
                for (int r = 1; r < M; r++)
                {
                    Debug.Assert(A[r - 1, c] <= A[r, c]);
                }
            }*/
            Console.WriteLine("Done Generating sorted array...");
        }

        static void Main_SimpleTest(string[] args)
        {
            int[,] A_normal = new int[,]{
                {1,2,3,4},
                {4,4,5,6},
                {10,11,12,13},
                {13,14,19,20},
                {13,14,19,20},
                {15,16,16,20}};

            foreach (int what in new int[] { 1, 4, 5, 10, 19, 13, 15, 20, 0 })
            {
                Console.WriteLine("To be found: {0}", what);
                var found = FindInSortedMatrix(A_normal, what);
                if (found != null)
                    Debug.Assert(A_normal[found.Item1, found.Item2] == what);
                else
                {
                    foreach (var line in A_normal)
                    {
                        Debug.Assert(line != what);
                    }
                }
            }

            // ============ Test Bsearch =========================
            var testArray = new int[] { 1, 2, 3, 4, 4, 5, 6, 9, 20 };
            Tuple<bool, int> res;
            foreach (var what in new int[] { 1, 2, 3, 4, 5, 6 })
            {
                res = Finder.BSearch(0, testArray.Length - 1, x => testArray[x], what);
                Debug.Assert(res.Item1 == true);
                Debug.Assert(testArray[res.Item2] == what);
            }
            res = Finder.BSearch(0, testArray.Length - 1, x => testArray[x], 0);
            Debug.Assert(res.Item1 == false);
            Debug.Assert(res.Item2 == -1);

            res = Finder.BSearch(0, testArray.Length - 1, x => testArray[x], 8);
            Debug.Assert(res.Item1 == false);
            Debug.Assert(res.Item2 == 6);

            res = Finder.BSearch(0, testArray.Length - 1, x => testArray[x], 30);
            Debug.Assert(res.Item1 == false);
            Debug.Assert(res.Item2 == testArray.Length - 1);

            // ================ Test Finder =======================
            foreach (int what in new int[] { 1, 4, 5, 10, 19, 13, 15, 20, 0 })
            {
                Console.WriteLine("To be found: {0}", what);
                var found = (new Finder(A_normal, what)).Find();
                if (found != null)
                    Debug.Assert(A_normal[found.Item1, found.Item2] == what);
                else
                {
                    foreach (var line in A_normal)
                    {
                        Debug.Assert(line != what);
                    }
                }
            }

            // ================== END ============================
            Console.Read();
        }

        /// <summary>
        /// Find a value in a sorted matrix
        /// </summary>
        /// <param name="A">The matrix</param>
        /// <param name="x">The value to be found</param>
        /// <remarks>
        /// The matrix is formed in a way that each column and row is sorted in increasing order.
        /// 
        /// * http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
        /// * http://stackoverflow.com/questions/10589975/find-number-in-sorted-matrix-rows-n-columns-in-olog-n
        /// </remarks>
        /// <returns>A tuple describe the found value's location in the matrix, or null if it's not found.</returns>
        static Tuple<int, int> FindInSortedMatrix(int[,] A, int x)
        {
            if (A == null) return null;
            int M = A.GetLength(0);
            int N = A.GetLength(1);
            int c1 = 0;
            int c2 = N - 1;
            while (c1 < M && c2 >= 0)
            {
                if (A[c1, c2] == x) return new Tuple<int, int>(c1, c2);
                else if (A[c1, c2] < x) c1++;
                else c2--;
            }
            return null;
        }
    }

    class Finder
    {
        public int[,] A;
        public int x;
        public Finder(int[,] A, int x)
        {
            this.A = A;
            this.x = x;
        }
        static public Tuple<bool, int> BSearch(int x1, int x2, Func<int, int> f, int toFind)
        {
            int L = x1;
            int U = x2;
            while (L <= U)
            {
                int p = (L + U) / 2;
                if (f(p).CompareTo(toFind) == 0)
                    return new Tuple<bool, int>(true, p);
                else if (f(p).CompareTo(toFind) > 0)
                    U = p - 1;
                else
                    L = p + 1;
            }
            return new Tuple<bool, int>(false, U);
        }

        public Tuple<int, int> Find()
        {
            int M = A.GetLength(0);
            int N = A.GetLength(1);
            int x1 = 0, y1 = 0, x2 = M - 1, y2 = N - 1;
            while (true)
            {
                var res = BSearch(x1, x2, (x) => A[x, y1], this.x);
                if (res.Item1) return new Tuple<int, int>(x1 + res.Item2, y1);
                x2 = res.Item2;
                if (x1 > x2) break;

                res = BSearch(x1, x2, x => A[x, y2], this.x);
                if (res.Item1) return new Tuple<int, int>(x1 + res.Item2, y2);
                x1 = res.Item2 + 1;
                if (x1 > x2) break;

                res = BSearch(y1, y2, y => A[x1, y], this.x);
                if (res.Item1) return new Tuple<int, int>(x1, y1 + res.Item2);
                y2 = res.Item2;
                if (y1 > y2) break;

                res = BSearch(y1, y2, y => A[x2, y], this.x);
                if (res.Item1) return new Tuple<int, int>(x2, y1 + res.Item2);
                y1 = res.Item2 + 1;
                if (y1 > y2) break;
            }
            return null;
        }
    }
}