Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• 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,

Consider the following matrix:

[
  [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]
]

Given target = 5, return true.

Given target = 20, return false.

Dp approach, o(n+m)

start from top-right corner of the matrix, if current element is greater than target, we can safely eliminate the current column and move left by one step. Otherwise, if current element is less than target, we can safely eliminate the current row and move down by one step.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return false;
        int r = 0, c = matrix[0].size() - 1;
        while(r < matrix.size() && c >= 0){
            if(matrix[r][c] == target){
                return true;
            }
            else if(matrix[r][c] < target){
                r++;
            }
            else{
                // matrix[r][c] > target
                c--;
            }
        }
        return false;
    }
};

Binary search solution in 2d matrix.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //binary search
        if(matrix.size() == 0 || matrix[0].size() == 0) return false;
        return binarySearch(matrix, target, 0, 0, matrix.size() - 1, matrix[0].size() - 1);
    }
    bool binarySearch(vector<vector<int>>& matrix, int target, int top, int left, int bottom, int right){
        // base condition
        if(top > bottom || left > right){
            return false;
        }
        if(left == right && bottom == top){
            return matrix[top][left] == target;
        }
        else{
            int midr = (top + bottom) / 2; // assume no overflow
            int midc = (left + right) / 2;
            if(matrix[midr][midc] < target){
                //right, down, rightdown area
                return binarySearch(matrix, target, midr + 1, left, bottom, right) || binarySearch(matrix, target, top, midc + 1, midr, right);
            }else if(matrix[midr][midc] > target){
                return binarySearch(matrix, target, top, left, midr - 1, right) || binarySearch(matrix, target, midr, left, bottom, midc - 1);
            }else{
                return true;
            }
        }
    }
};