# Easy C++ 12ms O(N) Solution. Not using a Binary Search

1. let me set m to be the rows of the matrix and n to be the cols of the matrix.
2. set i = 0 and j = n-1. then, matrix[i][j] = matrix[0][n-1], this element is located in the upper right corner of the matrix.
3. if target == matrix[i][j], then return true;

if target > matrix[i][j], because matrix[i][j] is the largest element of row i, target is larger than all the element in row i. DO. i++;

if target < matrix[i][j], because matrix[i][j] is the minimum element of col j, target is smaller than all the element in col j. DO. j--

1. if i > m - 1 or j < 0, break the while loop, and return false;

coding:

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.