# Search a 2D matrix

• For this problem, we need to search if an element is in the matrix. I know there is a good method to find the element in O(m + n) complexity. (search an element from top right element) My code is as followed:

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
for(int i = 0, j = matrix[0].length - 1; i < matrix.length && j >= 0;){
if(matrix[i][j] == target)
return true;
else if(matrix[i][j] < target)
i++;
else
j--;
}
return false;
}
}
``````

However, I still think this is not a very regular method to do that? Are there any other more conventional way to solve this problem?

• Could you please format the code? The last `}` is out of the code box.

• Your code assumes the matrix is sorted. If so, for large matrices it might be better do binary search (look at the matrix as an array of MxN elements - O(log(MxN)) complexity

• Here is the code that used binary search.
The matrix can be viewed as a one-dimensional sorted array. The value of element i in this array in the matrix is matrix[i/cols][i%cols].

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// Start typing your Java solution below
// DO NOT write main() function
int rows = matrix.length;
int cols = matrix[0].length;

int s = 0, e = rows* cols - 1;
while(s<=e){
int m = s+(e-s)/2;
if(matrix[m/cols][m%cols]==target)
return true;
else if(matrix[m/cols][m%cols]>target){
e = m -1;
}else{
s = m + 1;
}
}
return false;
}
}``````

• Actually, you can solve this problem by 2-pass binary search, which is in O(log m + log n)

• That's really neat. So much nicer than coding two binary search!

• This post is deleted!

• Note: to users who might be confused:
The problem @baojialiang described is this: Searching a 2D sorted matrix, which had not been added to OJ yet.

The answers below are based on the OJ problem Search a 2D matrix, which is similar, but has an added restriction:

The first integer of each row is greater than the last integer of the previous row.

Therefore, the solution @baojialing described works, but is not efficient enough compared to the binary search solution mentioned by @beijingyangbo.

• We can do much faster than O(log(MxN)). We would need only O(log m + log n) as described below :)

• O(log(m*n)) and O(log m + log n) they are mathematically equal...

• My apologies, I don't know why I made such a comment!

• yes, first do a binary search on the coloum[0] -> find the row (by using lower_bound type fuction)
then do a binary search on the found row, return true or false.

I think it is correct....if any flaw...plz comment it.

• I think we should also consider the case where rows* cols is too large for an int. When it is small matrix, this works awesome.

• the operator / &% may cost lots of time...

• You mean this?
My solution is exactly matching your description.

class Solution {

public:

``````bool searchMatrix(vector<vector<int> > &matrix, int target) {

auto end_it = upper_bound(matrix.cbegin(),
matrix.cend(),
target,
by_first_element);
if (end_it == matrix.cbegin()) return false;

for (auto row_it = matrix.cbegin();
row_it != end_it;
++row_it)
{
auto cell_it = lower_bound(row_it->cbegin(),
row_it->cend(),
target);
if (cell_it == row_it->cend()) continue;
if (*cell_it == target) return true;
}

return false;
}

static bool by_first_element(const int& b, const vector<int>& a)
{
return b < a.front();
}
``````

};

• The matrix is not sorted. Rows are sorted, first element for each row is sorted. One single binary search on the entire matrix is wrong.

• The matrix content is not sorted. Read the text.
Each row is sorted.
The first column is sorted.
Not the whole matrix.

You can do two binary searches.

• O(m + n) is not the best solution.
You can perform binary search for the first column, and than bynary search for each row with the firs value <= of target.

• read the description again yo not only you are the smartest ass.

• this is my code. I use twice binary search to seek the target. First search the rows, then the cols
It's log(m)+log(n)

``````class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int matrixRows = matrix.size();
int matrixCols = matrix[0].size();
if(matrixRows == 0)
return false;
if(matrixRows == 1)
return findCol(matrix[0], 0, matrix[0].size()-1, target);

if(target<matrix[0][0] || target > matrix[matrixRows-1][matrixCols-1])
return false;
if(target > matrix[matrixRows-1][0]) //if the target in the last row
return findCol(matrix[matrixRows-1], 0, matrixCols-1, target);

vector<int> rowFirstElement;
int idx=0;
while(idx<matrixRows)
{
rowFirstElement.push_back(matrix[idx][0]);
idx++;
}

int row = findRow(rowFirstElement, 0,  matrixRows-1, target);
if(row < 0 )
return false;
else
return findCol(matrix[row], 0, matrixCols-1, target);

}

int findRow(vector<int> &vec, int low, int high, int target)
{
int length = high - low;
if(length == 0)
return low;
if(length == 1)
{
if(vec[high] > target)
return low;
else
return high;
}

if(vec[low+length/2] > target)
findRow(vec, low, low+length/2-1, target);
else
findRow(vec, low+length/2, high, target);
}

bool findCol(vector<int> &vec, int low, int high, int target)
{
int length = high - low;
if(length == 0)
return target == vec[low];
if(length == 1)
return target == vec[low] || target == vec[high];

if(vec[low+length/2] == target)
return true;
else if(vec[length/2] > target)
findCol(vec, low, low+length/2-1, target);
else
findCol(vec, low+length/2, high, target);
}
};``````

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