content: package misc;
  
  public class SearchMatrix {
  
      /*
       * Search (find position of) a given key in 2D matrix. All rows and columns are sorted.
       *
       * Runtime Complexity:
       * Linear, O(m+n) where 'm' is number of rows and 'n' is number of columns.
       *
       * Memory Complexity:
       * Constant, O(1).
       *
       *
       * */
      protected static class Pair<K, V> {
  
          private K first;
          private V second;
  
          public static <K, V> Pair<K, V> createPair(K element0, V element1) {
              return new Pair<K, V>(element0, element1);
          }
  
          public Pair(K first, V second) {
              this.first = first;
              this.second = second;
          }
  
          public K getFirst() {
              return first;
          }
  
          public V getSecond() {
              return second;
          }
  
      }
  
  
      protected static Pair searchInMatrix(int matrix[][],
                                           int value) {
  
          int M = matrix.length; //rows
          int N = matrix[0].length; // columns
  
          // Let's start searching from top right.
          // Alternatively, searching from bottom left
          // i.e. matrix[M-1][0] can also work.
  
          int i = 0, j = N - 1;
  
          while (i < M && j >= 0) {
              if (matrix[i][j] == value) {
                  return new Pair(i, j);
              } else if (value < matrix[i][j]) {
                  // search left
                  --j;
              } else {
                  // search down.
                  ++i;
              }
          }
  
          return new Pair(-1, -1);
      }
  
  
      protected static void verifySearch(int[][] matrix) {
  
          for (int i = 0; i < matrix.length; ++i) {
              for (int j = 0; j < matrix[0].length; ++j) {
  
                  System.out.println("Verifying at " + i + ", " + j);
                  Pair val_loc = searchInMatrix(matrix, matrix[i][j]);
                  assert ((int) val_loc.first == i);
                  assert ((int) val_loc.second == j);
              }
          }
      }
  
  
      public static void main(String[] args) {
          int[][] matrix = new int[][]{
                  {1, 5, 45, 80, 81},
                  {6, 7, 48, 82, 83},
                  {20, 22, 49, 85, 86},
                  {21, 23, 50, 90, 92}
          };
  
          verifySearch(matrix);
      }
  }
  