74_Searcha2DMatrix - a920604a/leetcode GitHub Wiki

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size() , m=matrix[0].size();
        int i=0, j = m-1;
        int cur;
        while(i>-1 && i<n && j>-1 && j<m){
            cur = matrix[i][j];
            if(cur == target) return true;
            else if(cur<target) i++;
            else j--;
        }
        return false;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        // binary search
        int l=0, r = n-1;
        while(l<=r) {
            int mid = l+ (r-l)/2;
            if(matrix[mid][0]<=target && target <= matrix[mid][m-1]){
                cout<<mid<<endl;
                // binary search
                int a = 0, b = m-1;
                while(a<=b){
                    int m = a + (b-a)/2;
                    if(matrix[mid][m] == target) return true;
                    else if(matrix[mid][m]<target) a = m+1;
                    else b = m-1;
                }
                return false;
            }
            if(target > matrix[mid][m-1]) l = mid+1;
            else if(target< matrix[mid][0] ) r = mid-1;
        }
        return false;
    }
};

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