Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 3 Output: true Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target = 13 Output: false Example 3:
Input: matrix = [], target = 0 Output: false
Constraints:
m == matrix.length n == matrix[i].length 0 <= m, n <= 100 -104 <= matrix[i][j], target <= 104
public class Solution {
public bool SearchMatrix(int[][] matrix, int target) {
if(matrix.Length==0){
return false;
}
int r = matrix.Length;
int c = matrix[0].Length;
int total = r*c;
int lo = 0;
int hi = total;
while(lo<hi){
int mid = lo + (hi-lo)/2;
int row = mid/c;
int col = mid%c;
if(matrix[row][col]> target){
hi = mid;
}
else if(matrix[row][col]< target){
lo = mid+1;
}
else if(matrix[row][col]==target){
return true;
}
else{
return false;
}
}
return false;
}
}Time Complexity: O(logn)
Space Complexity: O(1)
