1 package POJ; 2  3 public class Main { 4  5     /** 6      *  7      * 11.6 Given an M x N matrix in which each row and each column is sorted in 8      * ascending order, write a method to find an element. 9      * 10      */11     public static void main(String[] args) {12         Main so = new Main();13     }14 15     public static Coordinate findElement(int[][] matrix, int x) {16         Coordinate origin = new Coordinate(0, 0);17         Coordinate dest = new Coordinate(matrix.length - 1,18                 matrix[0].length - 1);19         return findElement(matrix, origin, dest, x);20     }21 22     public static Coordinate findElement(int[][] matrix, Coordinate origin,23             Coordinate dest, int x) {24         if (!origin.inbounds(matrix) || !dest.inbounds(matrix)) {25             return null;26         }27         if (matrix[origin.row][origin.column] == x)28             return origin;29         if (!origin.isBefore(dest))30             return null;31         Coordinate start = (Coordinate) origin.clone();32         int diagDist = Math.min(dest.row - origin.row, dest.column33                 - origin.column);34         Coordinate end = new Coordinate(start.row + diagDist, start.column35                 + diagDist);36         Coordinate p = new Coordinate(0, 0);37 38         while (start.isBefore(end)) {39             p.setToAverage(start, end);40             if (x > matrix[p.row][p.column]) {41                 start.row = p.row + 1;42                 start.column = p.column + 1;43             } else {44                 end.row = p.row - 1;45                 end.column = p.column - 1;46             }47         }48         return partitionAndSearch(matrix, origin, dest, start, x);49     }50 51     private static Coordinate partitionAndSearch(int[][] matrix,52             Coordinate origin, Coordinate dest, Coordinate pivot, int elem) {53         // TODO Auto-generated method stub54         Coordinate lowerLeftOrigin = new Coordinate(pivot.row, origin.column);55         Coordinate lowerLeftDest = new Coordinate(dest.row, pivot.column - 1);56         Coordinate upperRightOrigin = new Coordinate(origin.row, pivot.column);57         Coordinate upperRightDest = new Coordinate(pivot.row - 1, dest.column);58         Coordinate lowerLeft = findElement(matrix, lowerLeftOrigin,59                 lowerLeftDest, elem);60         if (lowerLeft == null)61             return findElement(matrix, upperRightOrigin, upperRightDest, elem);62         return lowerLeft;63     }64 }65 66 class Coordinate implements Cloneable {67     int row;68     int column;69 70     public Coordinate(int r, int c) {71         row = r;72         column = c;73     }74 75     public boolean inbounds(int[][] matrix) {76         return row >= 0 && column >= 0 && row < matrix.length77                 && column < matrix[0].length;78     }79 80     public boolean isBefore(Coordinate p) {81         return row <= p.row && column <= p.column;82     }83 84     public Object clone() {85         return new Coordinate(row, column);86     }87 88     public void setToAverage(Coordinate min, Coordinate max) {89         row = (min.row + max.row) / 2;90         column = (min.column + max.column) / 2;91     }92 }