Kth Smallest Element in a Sorted Matrix

Java

public class Solution {
    /**
     * @param matrix: List[List[int]]
     * @param k: a integer
     * @return: return an integer
     */
		public int kthSmallest(int[][] matrix, int k) {
			if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return -1;
			int m = matrix.length;
			int n = matrix[0].length;
			
			int low = matrix[0][0];
			int high = matrix[m - 1][n - 1];
			
			while (low + 1 < high) {
				int mid = findMid(low, high);
				int cnt = helper(matrix, mid);
				if (cnt >= k) {                 //mid 有可能在矩阵中并不存在
					high = mid;
				} else {
					low = mid;
				}
			}
			return helper(matrix, low) >= k ? low : high;
		}
		
		private int findMid(int x, int y) {             //在正负不确定的情况下找中间数的套路
			if (x > 0 || y < 0) {
			return x + (y - x) / 2; //同号  
			} else {
				return x + y; //异号
			}
		}
		
		private int helper(int[][] matrix, int val) {
			int cnt = 0;
		  int m = matrix.length;
			int n = matrix[0].length;
       int i = 0, j = n - 1;
       while (i < m && j >= 0) {
           if (matrix[i][j] <= val) {
               cnt += j + 1;
               i++;
           } else {
               j--;
            }
        }
        return cnt;
		}
}