Search a 2D Matrix Problem Solution in Java | Binary Search
Problem Description :
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example 1 :
Input :
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
target = 15
Output :
false
Example 2 :
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
target = 5
Output :
true
Example 3 :
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
target = 34
Output :
true
In this problem, we have given 2 Dimensional Array and integer target. We have to find out if target is present in given matrix or not.
Given matrix elements are sorted so we can easily perform binary search and find out target is present or not.
Here we will see two solutions for this problem.
Solution 1 : Search a 2D Matrix in Java
import java.util.Scanner;
public class Search2DMatrix {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter row and column");
int row = sc.nextInt();
int column = sc.nextInt();
int[][] array = new int[row][column];
System.out.println("Enter array data");
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
array[i][j] = sc.nextInt();
}
}
System.out.println("Enter target");
int target = sc.nextInt();
System.out.println(searchMatrix(array, target));
}
public static boolean searchMatrix(int[][] matrix, int target) {
int i = 0;
int j = matrix[i].length-1;
while (i < matrix.length && j >= 0) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
j--;
} else {
i++;
}
}
return false;
}
}
Solution Explanation :
- Here we are start searching our target from last column of 1st row. So i = 0 and j = 4-1 = 3 becomes in our above example matrix.
- In while loop, we have to check for our i and j must not exceed given matrix index.
- Now check current element is target or not. If not,
- Go to else if, Check if target is greater than current element than decrement column value by 1.
- Otherwise increment row by 1.
Example Explanation :
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
target = 11
- i = 0, j = 3
- 0 < 3 && 3 >= 0 becomes TRUE
- if (7 == 11) becomes false
- else if (7 > 11) becomes false
- else i = 1
- i = 1, j = 3
- 1 < 3 && 3 >= 0 becomes TRUE
- if (20 == 11) becomes false
- else if (20 > 11) becomes TRUE
- j = 2
- i = 1, j = 2
- 1 < 3 && 2 >= 0 becomes TRUE
- if (20 == 11) becomes false
- else if (20 > 11) becomes TRUE
- j = 1
- i = 1, j = 1
- 1 < 3 && 1 >= 0 becomes TRUE
- if (11 == 11) becomes TRUE
- return TRUE
Solution 2 : Find given target in 2D Matrix using Binary Search in Java
import java.util.Scanner;
public class Search2DMatrix {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter row and column");
int row = sc.nextInt();
int column = sc.nextInt();
int[][] array = new int[row][column];
System.out.println("Enter array data");
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
array[i][j] = sc.nextInt();
}
}
System.out.println("Enter target");
int target = sc.nextInt();
System.out.println(searchMatrix(array, target));
}
public static boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) return false;
int rowSize = matrix.length;
int columnSize = matrix[0].length;
int low = 0;
int high = (rowSize * columnSize) - 1;
while (low <= high) {
int mid = (high + low) / 2;
if (matrix[mid/columnSize][mid%columnSize] == target) {
return true;
} else if (matrix[mid/columnSize][mid%columnSize] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return false;
}
}
Solution Explanation :
- Here we are using Binary Search algorithm for finding solution.
- Take low as 0 and high as row * column size.
- Loop until low becomes less than high.
- Get mid element.
- Here we are getting mid element through :
- Row = Divide mid with columnSize
- Column = Modulo of mid with columnSize
- If target is less than current element, assign low by mid + 1.
- Else assign high as mid - 1.
Comments
Post a Comment