Key points -
1) Search space - 0 to row*cols-1;
Reason - when directly divided by no of columns in a row
You get directly the row and col
Eg : 11 is mid and cols in a row is 4
11/4 -> 2nd row and 3 col in matrix
which is 12th ele -> 3rd row 4th ele
2) Once row and col is derived from mid
Same binary search logic is applied
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length;
int low = 0;
int high = rows * cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int row = mid / cols;
int col = mid % cols;
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
}
Top comments (0)