74. Search a 2D Matrix

https://leetcode.com/problems/search-a-2d-matrix/

1. Use iteration:

//4 ms    7.6 MB
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        if(matrix[0].empty()) return false;
        int m = matrix.size();
        int n = matrix[0].size();  
        for(int i = 0; i < m; i++){
            if(matrix[i][0] > target){
                int row = i - 1;
                if(row >=0){
                    for(int j = 0; j < n; j++)
                        if(matrix[row][j] == target)
                            return true;
                } else
                    return false;
            } else if(matrix[i][0] == target)
                return true;
        }
        int row = m - 1;
        if(row >=0)
            for(int j = 0; j < n; j++)
                if(matrix[row][j] == target)
                    return true;
        return false;
    }
};

2. Use binary search:

//8 ms    7.6 MB
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        int l = 0;
        int r = matrix.size() * matrix[0].size();
        int col = matrix[0].size();
        while(l < r){
            int median = l + (r - l)/2; 
            if (matrix[median / col][median % col] == target) {
                return true;
            } else if (matrix[median / col][median % col] > target) {
                r = median;
            } else {
                l = median + 1;
            }
        }
        return false;
    }
};