메트릭스에 특정값을 찾기 위해 만약 모든 2차원 배열요소를 검사한다면, N x N 즉 O(n ^2) 의 시간이 소요될 것이다. 이 보다 빠르게 검색하기 위해 수평 및 수직으로 값이 정렬되어 있다는 성질을 이용할 수 있다. 즉, 좌측하단 배열요소를 시작점으로 만약 검색하고자하는 값이 이보다 작으면 윗쪽으로, 이보다 크면 오른쪽으로 검색을 진행하여 계단식으로 검색을 진행할 수 있다.

이러한 알고리즘은 O(N + N) 즉 O(N)의 시간을 소요한다. 검색을 위해 좌측하단을 시작점으로 하였으나, 기술적으로 우측상단을 시작점으로 사용할 수도 있다. 하지만, 좌측상당 및 우측하단은 좌우상하 이동이 같은 방향으로 사용되므로 이용할 수 없다. 또한 메트릭스가 큰 경우에는 상하의 위치점을 Binary Search로 찾고 다시 좌우의 값이 정렬되어 있으므로 Binary Search를 다시 적용하여 보다 빠르게 (O(log N)) 찾을 수 있다.

public void RunTest()
{
    // Assumption : A[N,N]
    const int N = 4;
    int[,] A = new int[N, N] { 
        {10,  20,  30,  40},
        {15,  22,  33,  44},
        {25,  27,  41,  49},
        {35,  40,  50,  60}
    };

    bool found = NumberExists(A, 30);
    Console.WriteLine("Found 30? " + found);
}
        
bool NumberExists(int[,] A, int n)
{            
    int N = A.GetLength(0);
    int r = N - 1;
    int c = 0;

    while (c < N && r >= 0)
    {
        int val = A[r, c];
        if (val == n)
            return true;

        if (val > n)
            r--;
        else
            c++;
    }

    return false;
}