# Java Solution ...Finding the Row via binary search where target may exist

• here i am finding the row where the target may exist via binary search and then after getting the row, again applying binary search in it . Time Complexity , i suppose is O(logm +logn) (Pls correct me if I am wrong) ...

``````
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {

if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return false;

int i=0,j=matrix.length-1;

while(i<j)
{
int mid=i+(j-i)/2;
if(matrix[mid][matrix[0].length-1]==target)
return true;
else if(matrix[mid][matrix[0].length-1]<target)
i=mid+1;
else
j=mid-1;
}
while(target>matrix[i][matrix[0].length-1])
{
i++;
if(i<0 || i>=matrix.length)
return false;
}

int p=0;j=matrix[0].length-1;
while(p<=j)
{
int mid=(p+j)/2;
if(matrix[i][mid]==target)
return true;
else if(matrix[i][mid]<target)
p=mid+1;
else
j=mid-1;
}

return false;
}
}
``````

• FYI, O(logm+logn) is just the same as O(logmn). What's more u can combine ur two binary search into one. Example is as follows.

``````#define ma(a, i, j, n) (n ? a[j][i] : a[i][j])
...
row = 0;
for (int c = 0; c < 2; ++c) {
l = 0;
r = c ? matrix[0].size()-1 : matrix.size()-1;
while (l <= r) {
m = l+(r-l)/2;
t = ma(matrix, m, row, c);
if (target < t) {
r = m-1;
} else if (target > t) {
l = m+1;
} else {
return true;
}
}
if (r < 0) {
return false;
}
row = r;
}
return false;
...
``````

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