# O(log(mn)) solution considered (m*n) overflow

• Hi all,

I found most of the solutions given here consider the matrix as a sorted array, but that might cause overflow if m, n are large. I have a solution using binary search twice and it's pretty close to binary search in usual way as I compare target to the last element in each row instead of the first element.

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int iLo = 0;
int iHi = m-1;
while(iLo < iHi){
int iMid = (iLo + iHi)/2;
if(matrix[iMid][n-1] == target) return true;
else if(matrix[iMid][n-1] < target) iLo = iMid + 1;
else iHi = iMid;
}
int jLo = 0;
int jHi = n-1;
while(jLo < jHi){
int jMid = (jLo + jHi)/2;
if(matrix[iLo][jMid] == target) return true;
else if(matrix[iHi][jMid] < target) jLo = jMid + 1;
else jHi = jMid - 1;
}
return matrix[iLo][jLo] == target;
}
}``````

• If m and n are too large, it would be better to compute iMid = iLo + (iHi - iLo)/2 to make sure overflow doesn't occur even at this point!

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