CareerCup

Start with top right element
Loop: 
     Compare this element e with x
     i) if they are equal then return its position
    ii) e < x then move it to down
   iii) e > x then move it to left
   Repeat above 3 steps till you find element
If not found return false

Make a check at each step that the index is not out of bound.
Time Complexity: O(n)
Space Complexity: O(1)

The code in Java is as follows:

boolean search_element(int a[][],int key)
{                
        int m=a.length;
        int n=a[0].length;
        int k=0;
        while((k<m) && (n>=0))
        {
            if(key<a[k][n-1])
                n--;
            else if(key>a[k][n-1])
                k++;
            else if(key==a[k][n-1])
                return true;
        }
        return false;
}

Given input x, using binary search find the largest first element which is smaller than input.
Then use binary search in row to see if there is an element that matches x.

bool search2D(int ele, int **mat, unsigned row, unsigned col, unsigned &oRow, unsigned &oCol)
{
unsigned i = 0;
unsigned j = row;

if ((ele > mat[row][col]) || (ele < mat[0][0]))
{
return false;
}

while (i<j)
{
unsigned k = (i+j)/2;
if (mat[k][col] > ele)
{
j = k;
}
else if (mat[k][col] < ele)
{
i = k+1;
}
else
{
oRow = k;
oCol = col;
return true;
}
}

oRow = i;

if (mat[oRow][col] == ele)
{
oCol = col;
return true;
}

for (i=0,j=col; i<j;)
{
unsigned k = (i+j)/2;
if (mat[oRow][k] > ele)
{
j = k;
}
else if (mat[oRow][k] < ele)
{
i = k+1;
}
else
{
oCol = k;
return true;
}
}

if (mat[oRow][i] == ele)
{
oCol = i;
return true;
}

return false;
}

mng soln seems to be appropriate

An approach with O(m log n) complexity would be to perform binary search on every row... Can we do better than this?

class point
        {
            public int X {set; get; }
            public int Y {set; get; }
            public point(int x, int y)
            {
                this.X = x;
                this.Y = y;
            }
        }
    class Searching
    {
        public static point SearchIn2DSortedArray(int[,] arr, int Key)
        {
            int MaxX = arr.GetLength(1) - 1;
            int MaxY = arr.GetLength(0) - 1;

            if (MaxY < 1 || MaxX < 1)
                goto RETURN_KEY_NOT_FOUND;
            if(Key < arr[0,0] || Key > arr[MaxY, MaxX])
                goto RETURN_KEY_NOT_FOUND;

            int X = MaxX;
            int Y = 0;

            while (X >= 0 && Y <= MaxY)
            {
                if (Key == arr[Y, X])
                    return new point(Y, X);
                
                if(Key < arr[Y, X])
                {                    
                    X--;
                    continue;
                }

                if(Key > arr[Y, X])
                {
                    Y++;
                    continue;
                }
            }
        RETURN_KEY_NOT_FOUND:
            return new point(-1, -1);
        }
    }

class point
        {
            public int X {set; get; }
            public int Y {set; get; }
            public point(int x, int y)
            {
                this.X = x;
                this.Y = y;
            }
        }
    class Searching
    {
        public static point SearchIn2DSortedArray(int[,] arr, int Key)
        {
            int MaxX = arr.GetLength(1) - 1;
            int MaxY = arr.GetLength(0) - 1;

            if (MaxY < 1 || MaxX < 1)
                goto RETURN_KEY_NOT_FOUND;
            if(Key < arr[0,0] || Key > arr[MaxY, MaxX])
                goto RETURN_KEY_NOT_FOUND;

            int X = MaxX;
            int Y = 0;

            while (X >= 0 && Y <= MaxY)
            {
                if (Key == arr[Y, X])
                    return new point(Y, X);
                
                if(Key < arr[Y, X])
                {                    
                    X--;
                    continue;
                }

                if(Key > arr[Y, X])
                {
                    Y++;
                    continue;
                }
            }
        RETURN_KEY_NOT_FOUND:
            return new point(-1, -1);
        }
    }

class point
        {
            public int X {set; get; }
            public int Y {set; get; }
            public point(int x, int y)
            {
                this.X = x;
                this.Y = y;
            }
        }
    class Searching
    {
        public static point SearchIn2DSortedArray(int[,] arr, int Key)
        {
            int MaxX = arr.GetLength(1) - 1;
            int MaxY = arr.GetLength(0) - 1;

            if (MaxY < 1 || MaxX < 1)
                goto RETURN_KEY_NOT_FOUND;
            if(Key < arr[0,0] || Key > arr[MaxY, MaxX])
                goto RETURN_KEY_NOT_FOUND;

            int X = MaxX;
            int Y = 0;

            while (X >= 0 && Y <= MaxY)
            {
                if (Key == arr[Y, X])
                    return new point(Y, X);
                
                if(Key < arr[Y, X])
                {                    
                    X--;
                    continue;
                }

                if(Key > arr[Y, X])
                {
                    Y++;
                    continue;
                }
            }
        RETURN_KEY_NOT_FOUND:
            return new point(-1, -1);
        }
    }

Suppose we have 2D matrix with bottom left corner as starting point. Now compare the last element of first column and last row with the matching element. If the last elements are smaller then move to next diagonal element and repeat the above steps. If last element is bigger then we are sure that matching element should be present in current row or column so do binary search to find it.

A simple algo can be as below:
1) Given Matrix[i][j] where i and j are the rows and columns of the table.
2) If entered number, E is less than M[0][0] or greater than M[n][n] then print element does not present in matrix.
3) Check element start from first row and then subsequent rows .... E < = M[0][3]
then start for 1st row to check whether E=M[0][j] for j = 0,1,2,3
4) Return if you find suitable match or return "Element is not present in the given matrix"
5) End

Take a point at n/sqrt(2),m/sirt(2). Compare with key. If you find key bigger then this, that means key is in lower right rectangle. Space of this rectangle is n*m/2. If key is lower, key could be above this element or on left of it. Any way we split all array on 2 parts of about half space. Use same technic to split area left by half. At some moment area left wold be something like two intervals or one interval of single element. Any way it is trivial to use bsearch on it.
complexity O(log(N*M)) and O(1) space.

Cheers