Search a sorted 2D matrix

Question

M is a 2D matrix of integers (nXm) they are sorted in both row and column Write a function search(int s) that return the exact location of the number or Null. What would be the most efficient way to do so?

Answer 1

init: m[1..n(rows),1....m(columns)]

i=n,j=1

Start at (i,j):

STEP 1) if the value equals m(i,j) return (i,j)
STEP 2) if the value > m(i,j) go to step 1 with j+=1
STEP 3) else go to step 1 with i-=1

at each step if j or i is out of bound return no-solution.

The complexity of this solution is O(n+m) in case n=m the complexity is O(n)

I wonder if there is a log(n*m) solution like in binary search

EDIT another possible solution:

STEP 1)take the middle (n/2,m/2) of the matrix and compare it to the value
STEP 2) if the value equals m(i,j) return (i,j)
STEP 3) if the value is higher you can get rid from the first quarter  
STEP 4) if the value is lower you can get rid from the forth quarter
STEP 5) split the 3 other quarters to 2, a rectangle and a box, 
        send those both items to step 1 in a recursive manner

I am not sure about the efficiency of this solution: if R = N*M then T(R) = T(R/2) + T(R/4) + O(1)

Answer 2

Consider the below input:

1 2 3

4 5 6

7 8 9

The DuduAlul's algorithm would not find the location of the number 4 for example.

Answer 3

Say we have

1 2 5 7
2 4 7 9
3 5 8 9
5 6 9 9

Now we search for 6. You can see that there is a "strip" going from top right (5 7) to bottom left (5 6 7) where the values smaller than 6 flip to values bigger than 6 ("strip" marked with *):

1 2 5*7
2 4*7 9
3 5*8 9
5*6*9 9

So an algorithm would be:

• check if top left is bigger as your number -> return null
• check if bottom right is smaller as your number -> return null
• go the diagonal from top left down to bottom right until you find "the strip"
• follow the strip in both directions, until you find the number.

Answer 4

I just opened up notepad and wrote a bit, but I think this will do it in O(x) time, where x is the larger index between n and m. The worst case for this algorithm would be for the search term to be equal to the largest term in the array, for which this method will loop through n or m (whichever is larger) times. If that's going to be common, one can just start from the bottom right instead of the top left, and decrement indicies instead of incrementing them.

int[] SearchArray(int s, int[][] array)
{
    int i = 0;
    int j = 0;
    int n = array.GetLength(0);
    int m = array.GetLength(1);
    if (s > array[n][m])
            return null;
    while (i < n && j < m)
    {
        if (array[i][j] > s)
            return null;
        if (array[i][j] == s)
            return new int[]{i,j};
        try
        {
            if (array[i+1][j+1] < s)
            {
                    i++;
                    j++;
            }
            else if (array[i+1][j] > array[i][j+1])
                if (array[i+1][j] < s)
                    i++;
                else
                    j++;
            else if (array[i][j+1] > array[i+1][j])
                if (array[i][j+1] < s)
                    j++;
                else
                    i++;
            else if (array[i+1][j] == array[i][j+1])
                if (n < m)
                    i++;
                else
                    j++;
        }
        catch(IndexOutOfRangeException e)
        {
            if (i == n-1)
                j++;
            if (k == m-1)
                i++;
        }
    }
}

---

Edited for optimization and formatting