```
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0)
return false;
int rowToSearch = -1;
for(int i = 0; i < matrix.length; i++){
if(target == matrix[i][0]){
return true;
}
else if(target > matrix[i][0]){
rowToSearch++;
}
}
if(rowToSearch < 0)
return false;
int index = Arrays.binarySearch(matrix[rowToSearch], target);
if(index > 0) {
return true;
}
else {
return false;
}
}
```

}

explanation : check if target is equal to the first element of every row. if it is return true since we have found the number. if it is greater we must compare every first element of each row and stop when we find a target that is less than the first element of that row. the target must lie in the previous row.

Since it is sorted we can do a binary search in that row in log(n) time. since the two loops are separate the worst case is O(n) since the worst case is the one where the target is in the last row which means we made n comparisons and searched the last row in log(n) comparisons.