Searching in a 2D matrix.
Here’s a Java program that demonstrates searching for a target value in a 2D matrix:
public class MatrixSearch {
public static boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int rows = matrix.length;
int cols = matrix[0].length;
int low = 0;
int high = rows * cols - 1;
while (low <= high) {
int mid = (low + high) / 2;
int midValue = matrix[mid / cols][mid % cols];
if (midValue == target) {
return true;
} else if (midValue < target) {
low = mid + 1;
} else {
high = 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 = 16;
boolean found = searchMatrix(matrix, target);
if (found) {
System.out.println("Target found in the matrix.");
} else {
System.out.println("Target not found in the matrix.");
}
}
}
In this program, the `searchMatrix` method implements the binary search algorithm to search for a target value in the given 2D matrix. The matrix is treated as a flattened array, and the search is performed by finding the middle element and comparing it with the target value. Based on the comparison, the search range is narrowed down until the target is found or the search range is exhausted.
In the `main` method, a sample 2D matrix is defined, along with the target value. The `searchMatrix` method is then called to search for the target value in the matrix. The program prints a message indicating whether the target was found or not.
Note that the provided matrix should be sorted in ascending order, both row-wise and column-wise, for the binary search to work correctly.