# Share my two O(logm + logn) solutions

• Solution1:

Treat the matrix as a sorted list, and use binary search.

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

int height = matrix.size();
int width = matrix[0].size();

if(matrix[0][0] > target || matrix[height-1][width-1] < target)	return false;

int head = 0,tail = height*width-1;
int mid,midRow,midCol;

{
midCol = mid%width;
midRow = mid/width;
if(matrix[midRow][midCol] < target)
else if(matrix[midRow][midCol] > target)
tail = mid-1;
else
return true;
}
return false;
}
};
``````

Solution2:

Use binary search for matrix[i][0] to find the row where target is in, and then use binary search for matrix[row][j] to find target. This solution is better because it avoids multiplication overflow(height*width) and / and % while it's complexity is the same as solution1.

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

int heigth = matrix.size();
int width = matrix[0].size();

if(matrix[0][0] > target || matrix[heigth-1][width-1] < target)		return false;

int tail = heigth-1;
int mid;
while(head != tail && matrix[tail][0] > target)
{
if(matrix[mid][0] < target)		head = mid;
else if(matrix[mid][0] > target)	tail = mid-1;
else 	return true;
}
int row = tail;
{
if(matrix[row][mid] < target)
else if(matrix[row][mid] > target)
tail = mid -1;
else return true;
}
return false;
}
};``````

• How come they have the same time complexity? The first one is O(logm+logn), the second is O(logm*logn)

• Nonsense, the first one is O(log(m * n)) = O(log(m) + log(n)) and the second one is O(log(m) + log(n)). They have the same complexity!!

• why mid = (head+tail+1)/2; need to plus 1?

• I like your 2nd solution, which considered overflow

• Same Solution in Java

``````public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0)
return false;

int heigth = matrix.length;
int width = matrix[0].length;

if(matrix[0][0] > target || matrix[heigth-1][width-1] < target)
return false;

int head = 0, tail = heigth-1, mid;

while(head != tail && matrix[tail][0] > target){

if(matrix[mid][0] < target)
else if(matrix[mid][0] > target)
tail = mid-1;
else
return true;
}

int row = tail;
tail = width-1;

if(matrix[row][mid] < target)
else if(matrix[row][mid] > target)
tail = mid -1;
else
return true;
}
return false;
}
``````

• the reason why
is to deal with the case like this

``````[[1],[3]]
1
``````

if not plus 1 the head will always stuck at the same place

• This post is deleted!

• Can somebody tell me why to find a search row this formula is used -

``````mid = (head+tail+1)//2
``````

``````mid = (head+tail)/2
``````

• @juntong
Your code will not work for below input:

[[1,3,5,7],[2,11,16,30],[4,13,24,50]]
30

Result: False