Problem: 74. Search a 2D Matrix
Approach
/**
Definitely binary search
2 steps:
- search for which row the target should fall into
- then search within that row for the target
How to search for which row
hasRow = false;
int rowIdx = -1;
leftRow and rightRow
while (leftRow <= rightRow) {
int midRow;
if (target within midRow) {
hasRow = true;
rowIdx = midRow;
}
if (target < midRow[0]) {
right = midRow - 1;
} else if (target > midRow[size - 1]) {
left = midRow + 1;
}
}
if not found row: return false;
else, find within the row
*/
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
boolean hasRow = false;
int rowIdx = -1;
int leftRow = 0;
int rightRow = matrix.length - 1;
int columns = matrix[0].length;
while (leftRow <= rightRow) {
int midRow = (leftRow + rightRow) / 2;
if (target >= matrix[midRow][0] && target <= matrix[midRow][columns - 1]) {
hasRow = true;
rowIdx = midRow;
break;
} else if (target < matrix[midRow][0]) {
rightRow = midRow - 1;
} else if (target > matrix[midRow][columns - 1]) {
leftRow = midRow + 1;
}
}
if (!hasRow) {
return false;
}
int left = 0;
int right = columns - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == matrix[rowIdx][mid]) {
return true;
} else if (target < matrix[rowIdx][mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
}
}
Top comments (0)