Find an element in matrix in which rows and columns are sorted

Problem

Given a matrix in which each row and each column is sorted, write a method to find an element in it.

Example

    1  4  7   13

    2  5  9   15

    3  6  10  16

Solution
Here we can have 2 cases -

1. Case when array is sorted such that last element of nth row is less than first element of n+1 th row
2. Generic case - simply put rows and columns

CASE 1 - If last element of each row is less than first element of next row

If the matrix is sorted in a way that the last element of each row is less than the first element of the next row, you can run a binary search on the first column to find out in what row that number is, and then run another binary search on the row.
Eg.

1   4  5   6

7   8  10  14

16 18  20  24

This algorithm will take O(log C + log R) time, where C and R are, respectively the number of rows and columns. Using a property of the logarithm, one can write that as O(log(C*R)), which is the same as O(log N), if N is the number of elements in the array. This is almost the same as treating the array as 1D and running a binary search on it.


CASE 2 - Generic case

But the matrix could be sorted in a way that the last element of each row is not less than the first element of the next row:

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

Method 1 - Divide and conquer using Quad Partitions
Note that don't get alarmed  by Quad Partitions, it is simply 4 partitions of 2D matrix.
We are kind-of doing a 2D binary search here. Each time we find the center of the matrix. If that is the element we are looking for, then return it. Notice that the center divide the matrix into four parts: upper-left, upper-right, bottom-left and bottom-right.

A|B
---
C|D

Suppose if y is the center of the matrix, and a,b,c,d are elements of matrix such that a ∈ A and b ∈ B, c ∈ C, d ∈ D,  a<y <d, and a<c and b < d.

• Therefore, if the element we are looking for, say x is less than the center, then it cannot be in the bottom-right part, where every elements are even greater than the center.
  

  x < y implies x lies in A, B and C.

• If the element we are searching is greater than the center, then it cannot be in the upper-left part.
  

  x > y implies it can be in B C or D.

Hence, each time we approximately eliminate 1/4 of the entire matrix. Therefore we have the recursion:

T(n)=3T(n/4)+O(1), 

T(n) = O(n^log4(3)) = O(n^0.7925)

Pseudocode

def find(Arr,x):
    a,b = Arr.shape // a=rowsize, b=col size
    i = a /2
 j = b /2
 y = Arr[i,j];
 if(x==y)
  return i,j;
 else 
  A = Arr[0:i,0:j];
  B = Arr[0:i,j+1:b];
  C = Arr[i+1:a,0:j];
  D = Arr[i+1:a, j+1:b]
  if(x>y)
   return (find(B,x),find(C,x),find(D,x))
  else
   return (find(A,x),find(B,x),find(C,x))

Here is a code in java

public static Pair<Integer> findInMatrix(int[][] data, int rowLow,
        int rowHigh, int colLow, int colHigh, int element) {
    if (rowLow > rowHigh || colLow > colHigh)
        return null;
    new LinkedList<Pair<Integer>>();
    int rowMid = (rowLow + rowHigh) / 2;
    int colMid = (colLow + colHigh) / 2;
    int mid = data[rowMid][colMid];
    if (mid == element)
        return new Pair<Integer>(rowMid, colMid);
    else if (element < mid) {
        Pair<Integer> topLeft = findInMatrix(data, rowLow, rowMid - 1,
                colLow, colMid - 1, element);
        if (topLeft == null) {
            Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
                    colMid, colHigh, element);
            if (topRight == null) {
                Pair<Integer> bottomLeft = findInMatrix(data, rowMid,
                        rowHigh, colLow, colMid - 1, element);
                return bottomLeft;
            } else
                return topRight;
        } else
            return topLeft;
    } else { // element > mid
        Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
                colMid + 1, colHigh, element);
        if (topRight == null) {
            Pair<Integer> bottomLeft = findInMatrix(data, rowMid + 1,
                    rowHigh, colLow, colMid, element);
            if (bottomLeft == null) {
                Pair<Integer> bottomRight = findInMatrix(data, rowMid,
                        rowHigh, colMid + 1, colHigh, element);
                return bottomRight;
            } else
                return bottomLeft;
        } else
            return topRight;
    }
}

Method 2 - Binary search on each row
Another simple approach will be to run a loop on the rows. Now take 1D array of the row, find the element in it, if find break the loop, otherwise continue till end of the loop.
Looping on array takes O(n) time and searching in each element will take log n time.
This will take O(n log n) time.

Method 3 - Stepwise search
Another approach is we can start with top right, or bottom left element. Compare the element to be searched with element, and accordingly move a step down. Here is the approach, if we start with top right element:

Suppose we have to find x in the array.

1. Start with top right element
2. Loop: compare this element e with x
   1. if they are equal then return its position
   2. x > e then move it to down (if out of bound of matrix then break return false)
   3. x < e then move it to left (if out of bound of matrix then break return false)
3. repeat the i), ii) and iii) till you find element or returned false

Suppose we search for 13 in below array:

(image courtesy)
Time Complexity: O(n) OR O(n+m) if n!=m.

Java code

public static Pair<Integer> FindElem(int[][] mat, int elem, int M, int N) {
    int row = 0;
    int col = N - 1;
    while (row < M && col >= 0) {
        if (mat[row][col] == elem) {
            return new Pair<Integer>(row, col);
        } else if (mat[row][col] > elem) {/go left
            col--;
        } else {//go down
            row++;
        }
    }
    return null;
}

References
http://tianrunhe.wordpress.com/2012/03/31/find-an-element-in-a-matrix-whose-rows-and-columns-are-sorted/
http://stackoverflow.com/questions/10589975/find-number-in-sorted-matrix-rows-n-columns-in-olog-n
http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/
http://leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
http://leetcode.com/2010/10/searching-2d-sorted-matrix-part-iii.html