without using any methods stored in the program such as array.sort etc. (10 poin
ID: 3731857 • Letter: W
Question
without using any methods stored in the program such as array.sort etc.
(10 points) A method to find an element in a 2-dimensional array Write a method called findElement that takes as input a two-dimensional array of integers and an int n. Assume that the array received as input is a matrix and it has been sorted. Then the method must find the position of the element n inside the matrix. The method returns an array of integers with two elements. If n is in the matrix than the elements correspond to the row and the column of n, otherwise the elements are both equal to -1. To find the element n inside the matrix implement the following algorithm 1. Start by looking at the bottom left element of the matrix 2. Compare the element with the input. 3. If they are equal, then create/initialize the array with the correct postion and return it. 4. If n is smaller than the element you are looking at, then move up in the matrix by one position 5. If n is greater than the element you are looking at, then move to the right in the matrix by one position. 6. Go back to step 2, until you either find the element or you get out of bounds If the element if not in the matrix, the method returns the array [-1, -1,1. Consider the following array int[] C] xt0, 22, 32], 13, 26, 37}, 17, 26, 37-, 115, 35, 39}, 134, 39, 45j) Then: » findElement(x, 15) returns {3,0} since the element 15 is in the fourth row, first column of the matrix. The method will start by comparing 15 with the bottom left element, in this case 34. Since 15 is smaller than 34, the method will move up by one position in the matrix and compare 15 with 15. The two values are equal, therefore the method can return the position of 15 inside the matrix · findElement(x, 18) returns {-1, -1} since there is no element equal to 18 inside the array The method will start by comparing 18 with 34. Since 18 is smaller than 34, the method will move up by one position in the matrix and compare 18 with 15. Since 18 is greater than 15, the method will now move one position to the right inside the matrix and compare 18 with 35 Since 18 is smaller than 35, the method will move up and compare 18 to 26. Since 18 is smalleir than 26, the method will keep moving up and it compares 18 to 26. It will then move up again and compare 18 to 22. 18 is smaller than 22 and therefore the method will move up by oneExplanation / Answer
public class FindInMatrix{
/* Searches the element x in mat[][]. If the
element is found, then prints its position
and returns true, otherwise prints "not found"
and returns false */
public static int[] findElement(int[][] mat, int x) {
int n = mat.length;
int i = 0, j = n-1; //set indexes for top right
// element
while ( i < n && j >= 0 )
{
if ( mat[i][j] == x )
{
//System.out.print("n Found at "+ i + " " + j);
return new int[]{i, j};
}
if ( mat[i][j] > x )
j--;
else // if mat[i][j] < x
i++;
}
//System.out.print("n Element not found");
return new int[]{-1, -1}; // if ( i==n || j== -1 )
}
// driver program to test above function
public static void main(String[] args) {
int mat[][] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50} };
findElement(mat, 29);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.