Description

Submission

class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
if(matrix.empty()) return false;
if(matrix[0].empty()) return false;

    int nRow = matrix.size();
    int nCol = matrix[0].size();

    int i = 0, j = nRow - 1;
    while(i < j) {
        int mid = (i + j) / 2;
        if(target > matrix[mid][0]) i = mid + 1;
        if(target < matrix[mid][0]) j = mid - 1;
        if(target == matrix[mid][0]) i = j = mid;
    }
    int row = i;
    if(matrix[row][0] > target) row--;
    if(row < 0) return false;

    i = 0;
    j = nCol - 1;
    while(i < j) {
        int mid = (i + j) / 2;
        if(target > matrix[row][mid]) i = mid + 1;
        if(target < matrix[row][mid]) j = mid - 1;
        if(target == matrix[row][mid]) i = j = mid;
    }
    return matrix[row][i] == target;
}

};