1) Input matrix[n][n] and element e
2) Start with top right element
i
= 0; j= n-1;
3) while termination condition:
a)
if matrix[i][j]==e;
Return
position
b)
matrix[i][j]<e then move it to down (i++)
c)
matrix[i][j]>e then move it to left (j--).
Repeat a, b and c.
Terminating conditions:
1.
element e found.
2.
i>=row or j<0
public class SearchSortMat {
private static void findElement(int[][] matrix,int element) {
int row = matrix.length;
int i = 0;
int j = matrix[0].length-1;
while(i<row &&
j>=0) {
if(element ==
matrix[i][j]) {
System.out.println(element+" found at ("+i+","+j+")");
break;
} else if(element>matrix[i][j])
{
i++;
} else {
j--;
}
}
if(i>=row || j<0) {
System.out.println(element + " not found !!");
}
}
public static void main(String[] args) {
int[][] matrix = {{20, 30, 40, 50},
{25,
35, 45, 55},
{37,
39, 47, 58},
{42,
43, 49, 60}};
int element = 43;
findElement(matrix,
element);
}
}
Time Complexity: O(n)
No comments:
Post a Comment