Question

A speedy Decrease-and-Conquer search.

Use your newly acquired knowledge of “Decrease-and-Conquer” algorithm design strategy to design a O( n ) algorithm to search for a given number in an n × n matrix in which every row and every column in this matrix is sorted in increasing order

Write your algorithm as an elegant java method named findElement(int [][] arr, int element) that returns the index of that element in the array as a small int array made of 2 cells only; the first for the row and the second for the column.

if that element is not in the array your method shall return {-1,-1}.

Don't worry there is only one solution to all our test cases.

For example:

Test	Input	Result
findElement(arr, item);	8 15 9 19 find 9	1 0
findElement(arr, item);	8 15 9 19 find 10	-1 -1
findElement(arr, item);	8 15 19 9 22 26 16 23 30 find 23	2 1

Answer 1

Java code with findElement() method :

public class DecreaseConquerSearch{
   // Method to find item in matrix arr
       // if found return index of item
       // else return array of {-1,-1}
       private static int[] findElement(int[][] arr, int item)
   {
           int n = arr.length;
  
   int i = 0, j = n - 1;
  
   while (i < n && j >= 0) {
   if (arr[i][j] == item) {
       int[] res = {1,2};
   return res;
   }
   if (arr[i][j] > item)
   j--;
   else
   i++;
   }
  
   int[] res = {-1,-1};
   return res;
   }
  
  
public static void main(String[] args) {
int[][] arr = { {8, 15, 19},
               {9, 22, 26},
               {16, 23, 30}};
int item = 23;
  
int[] res = findElement(arr, item);
  
System.out.print(res[0] + " " + res[1]);
}
}

Output :

1 2

Hope you like it

Any Query? Comment Down!

I have written for you, Please up vote the answer as it encourage us to serve you Best !