Given sorted m x n matrix (each row starts after last of previous), search for a target using O(log(M*N)) binary search.
Input: [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=3 → Output: true
Treat as flat array: row = mid/n, col = mid%n.
- lo=0, hi=m*n-1.
- mid=lo+(hi-lo)/2; val=matrix[mid/n][mid%n].
- Compare to target; adjust lo/hi.
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m=matrix.length, n=matrix[0].length, lo=0, hi=m*n-1;
while (lo<=hi){
int mid=lo+(hi-lo)/2, val=matrix[mid/n][mid%n];
if (val==target) return true;
else if (val<target) lo=mid+1; else hi=mid-1;
}
return false;
}
}
- Time Complexity: O(log(M*N))
- Space Complexity: O(1)