Write an efficient algorithm that searches for a value in an m x n matrix.

Matrix can have two forms. Solve it for each form of the matrix. This matrix has the following properties:

Version 1
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

For example,

  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]

Then,
search(mat, 11) = true
search(mat, 2) = false
search(mat, 17) = false

Version 2
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

For example,

  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]

Then,
search(mat, 11) = true
search(mat, 3) = false
search(mat, 17) = true

version 1 : First element is greater then last element of previous row
At each row we can know in O(lgn) time if the desired element is there or not. But which row to look into. As the rows are wrapped around in sorted order so, we can easily find the row which may contain the target. So, we will do a vertical binary search over first column to identify the row.

1. If the mid is greater than the key than we know that this row and all next rows do not contain the mid. So, search upward. 
2. On the other hand if mid is less than the key than either this row may contain the key or all subsequent rows. 

Now, we found a candidate row. We now do normal horizontal binary search in that row to search the key. Below is implementation of this idea which simply runs in O(lgn) time .

public boolean searchMatrix1(int[][] matrix, int target) {
    if(matrix == null || matrix.length == 0){
        return false;
    }
    
    //find the row
    int n = matrix.length;
    int m = matrix[0].length;
    
    int row = -1;
    int rl = 0;
    int rh = n-1;
    while(rl <= rh){
        int mid = (rl+rh)/2;
        if(matrix[mid][0] == target || matrix[mid][m-1] == target){
            return true;
        }
        else if(matrix[mid][0] > target){
            rh = mid-1;
        }
        else{
            if(matrix[mid][m-1] > target){
                row = mid;
                break;
            }
            else{
                rl = mid+1;
            }
        }
    }
    
    if(row == -1){
        return false;
    }
    
    //search in the row
    int col = -1;
    int cl = 0;
    int ch = m-1;
    while(cl <= ch){
        int mid = (cl+ch)/2;
        if(matrix[row][mid] == target){
            return true;
        }
        else if(matrix[row][mid] > target){
            ch = mid-1;
        }
        else{
            cl = mid+1;
        }
    }
    
    return false;
}

Version 2: Rows and Columns are sorted in increasing order
Now, the rows and columns are sorted but there is no guarantee that start of a row is greater than the end of previous row i.e. the rows are not wrapped around in sorted order. How do we search for the key? Can we do the same approach of finding the row first and then the element in that row? What are the challenges?

Note that, if we try to find row and then the element in that row it will not work in this case. For example, in the following matrix if we search for 6 then we end up in searching 2nd row where the key is not there. Also, We may end up searching the whole matrix yielding O(n^2) time worst case complexity.

  [1,   4,  7],
  [2,   5,  8],
  [3,   6,  9]

How we can improve the solution? Note that, as all rows and cols are sorted so, we can try a greedy approach to check if a row and column can contain the key or not. For example, to search 6 in the bove matrix we can start from top-right corner (for example, 7). As 7 is higher then key 6 so, 6 can’t contain in this column(why?). So, we basically remove column from search.

  [1,   4,  7],
  [2,   5,  8],
  [3,   6,  9]

Now, we resume search in the new top-right corner 4. As 4 is less than 6 then the row can’t contain the key. So, we remove this row from consideration.

  [1,   4,  7],
  [2,   5,  8],
  [3,   6,  9]

Next, we resume search in the new top-right corner 5. As 5 is less than 6 then the row can’t contain the key. So, we remove this row from consideration.

  [1,   4,  7],
  [2,   5,  8],
  [3,   6,  9]

Next, we resume search from new top-right 6 and voila! We found our key. What is the worst case complexity? The worst case scenario would be that we are searching for the key at the bottom-left corner of the matrix. In this case at each step we shrink search space row and column by one. So, worst case complexity is O(max{n,m}) i.e. O(n) time. Below is a simple implementation of this idea.

public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix == null && matrix.length == 0){
        return false;
    }
    int n = matrix.length;
    int m = matrix[0].length;
    int r = m-1;
    int t = 0;
    
    
    while(t < n && r >=0){
         if(matrix[t][r] == target){
             return true;
         }
         else if(matrix[t][r] > target){
             r--;
         }
         else{
             t++;
         }
    }
    
    return false;
}