⬅ Previous Topic
Row with Maximum Number of 1'sNext Topic ⮕
Search in Row and Column-wise Sorted Matrix⬅ Previous Topic
Row with Maximum Number of 1'sNext Topic ⮕
Search in Row and Column-wise Sorted MatrixTopic Contents
You are given a 2D matrix of integers with the following properties:
Your task is to determine whether a given target number exists in the matrix.
If the number exists, return true
; otherwise, return false
.
m
rows and n
columns.start = 0
and end = m * n - 1
.start ≤ end
:mid = (start + end) / 2
.mid
to 2D coordinates: row = mid / n
, col = mid % n
.matrix[row][col] == target
, return true
.matrix[row][col] < target
, move start = mid + 1
.matrix[row][col] > target
, move end = mid - 1
.false
if target not found.public class MatrixSearch {
public static boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length;
int start = 0;
int end = rows * cols - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
int row = mid / cols; // Map 1D mid to 2D row
int col = mid % cols; // Map 1D mid to 2D col
if (matrix[row][col] == target) return true;
else if (matrix[row][col] < target) start = mid + 1;
else end = mid - 1;
}
return false;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 3, 5, 7},
{10, 11, 16, 20},
{23, 30, 34, 60}
};
int target = 3;
System.out.println("Found: " + searchMatrix(matrix, target));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | The target is found at the very first middle index. |
Average Case | O(log (m * n)) | The binary search is applied over a virtual 1D array of m * n elements. |
Worst Case | O(log (m * n)) | The binary search checks until one element is left, typical of a logarithmic search space. |
O(1)
Explanation: The algorithm uses constant space, no extra data structures are used apart from a few variables.
⬅ Previous Topic
Row with Maximum Number of 1'sNext Topic ⮕
Search in Row and Column-wise Sorted MatrixYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.