Find number in sorted matrix
Given an n x n matrix, where every row and column is sorted in increasing order. Given a number k, how to decide whether this k is in the matrix. OR Search number in a row wise and column wise sorted matrix.
Lets understand the problem statement graphically and it will be more clear,
There are many approach to solve this problem, Lets see few of them.
Approach 1:
Check for the number one by one by looking at each element of the array.
This approach is not efficient as in worst case we need to traverse complete matrix to identify whethet element is present or not.
Approach 2:
As matrix ix sorted, we can apply binary search on each row and identify whether element is present or not.
Approach 3:
In this approach, we will start our search by looking at Right most element of first row.
Given an n x n matrix, where every row and column is sorted in increasing order. Given a number k, how to decide whether this k is in the matrix. OR Search number in a row wise and column wise sorted matrix.
Lets understand the problem statement graphically and it will be more clear,
Algorithm
There are many approach to solve this problem, Lets see few of them.
Approach 1:
Check for the number one by one by looking at each element of the array.
This approach is not efficient as in worst case we need to traverse complete matrix to identify whethet element is present or not.
Approach 2:
As matrix ix sorted, we can apply binary search on each row and identify whether element is present or not.
Approach 3:
In this approach, we will start our search by looking at Right most element of first row.
- If Current Element = Search element, Return True, element found.
- If Current Element < Search element, It means all element on left of current element are smaller and no need to look on left. Check element on next column.
- If Current Element > Search element, It means all element on below current element are higher and no need to look down. Check element in left side on same row.
Search in a row wise and column wise sorted matrix Java Program
package javabypatel;
public class SearchElementInSortedRowColumnMatrix {
public static void main(String[] args) {
new SearchElementInSortedRowColumnMatrix();
}
public SearchElementInSortedRowColumnMatrix() {
int[][] arr = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}
};
int toSearch=10;
int column=arr[0].length-1;
int row=0;
boolean isFound=false;
while(row<arr.length && column>=0){
if(arr[row][column] == toSearch){
isFound=true;
break;
}else if(toSearch > arr[row][column]){
row++;
}else{
column--;
}
}
System.out.println(isFound);
}
}
You may also like to see
Count zeros in a row wise and column wise sorted matrix
Find Largest and Smallest number in Array
Find middle element of a linked list
Union and Intersection of Two Sorted Arrays
Merge two sorted arrays in Java
How is ambiguous overloaded method call resolved in java
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
Post a Comment