gistfile1.txt

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rows = matrix.length;
        if (rows == 0) {
            return false;
        }
        int cols = matrix[0].length;
        if (cols == 0) {
            return false;
        }
        int rowdiv = (int) Math.sqrt(rows);
        int coldiv = (int) Math.sqrt(cols);
        for (int r = 0; r < rows; r += rowdiv) {
            for (int c = 0; c < cols; c += coldiv) {
                int endr = Math.min(rows - 1, r + rowdiv);
                int endc = Math.min(cols - 1, c + coldiv);
                int begin = matrix[r][c];
                int end = matrix[endr][endc];
                if (target <= end && target >= begin) {
                    int curc = endc;
                    int curr = r;
                    while (curc >= c && curr <= endr) {
                        if (target > matrix[curr][curc]) {
                            curr += 1;
                        } else if (target < matrix[curr][curc]) {
                            curc -= 1;
                        } else {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }
}