A recursive method for finding ordered two dimensional arrays

  • 2020-04-01 02:07:10
  • OfStack

Given an ordered two-dimensional array, each row is incremented from left to right, and each column is incremented from top to bottom.
Suppose a 4-by-4 ordered two-dimensional array:
                  1                   2                   8                   9
                  2                   4                   9                   12
                  4                   7                   10               13
                  6                   8                   11               15
The number to look for is 6.
Algorithm is the core idea, first in the upper left corner number 9, because nine is greater than 6, so can rule out larger than 9 Numbers, which is the fourth column, and then take 8, in the same way to rule out the third column, and then take 2, is smaller than 6, smaller than 2 Numbers could be eliminated, which is the first line, in the same way take 4, eliminate the second line, take 7, eliminate the second column, take 4, eliminate the third line, take 6, are equal, return true.
Here we use the recursive implementation, the code is:

public class FindMatrixNumber {
 private static FindMatrixNumber instance;
 private static boolean found = false;
 public static FindMatrixNumber getInstance() {
  if (instance == null) {
   instance = new FindMatrixNumber();
  }
  return instance;
 }
 public static boolean find(int matrix[][], int number) {
  if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
   return false;
  } else {
   System.out.println("****Start finding****");
   findMatrixNumber(matrix, matrix.length, 0, matrix[0].length,
     number);
   System.out.println("*****End finding*****");
  }
  return found;
 }
 private static void findMatrixNumber(int matrix[][], int rows, int row,
   int columns, int number) {
  if (row > rows - 1)
   return;
  int cornerNumber = matrix[row][columns - 1];
  System.out.println(cornerNumber);
  if (cornerNumber == number) {
   found = true;
   return;
  } else if (cornerNumber < number) {
   findMatrixNumber(matrix, rows, ++row, columns, number);
  } else if (cornerNumber > number) {
   findMatrixNumber(matrix, rows, row, --columns, number);
  }
 }
}

The test code is:

public class TestFindMatrixNumber {

 public static void main(String[] args) {
  int matrix[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
  System.out.println(FindMatrixNumber.find(matrix, 6));
 }

}

The test code runs as follows:

****Start finding****
9
8
2
4
7
4
6
*****End finding*****
true


Related articles: