在一个排序矩阵中找从小到大的第 k 个整数。
排序矩阵的定义为：每一行递增，每一列也递增。

在线评测地址：领扣题库官网
样例 1:

输入:
[
  [1 ,5 ,7],
  [3 ,7 ,8],
  [4 ,8 ,9],
]
k = 4
输出: 5

样例 2:

输入: 
[
  [1, 2],
  [3, 4]
]
k = 3
输出: 3

算法：二分

题目中矩阵n行m列，每行每列都是单调的，我们可以按照行或者列做
把n行当成n个数组
即求n个有序数组里第k小值是多少

如果序列有序，则可以用一种更有效率的查找方法来查找序列中的记录，这就是折半查找法，又称为二分搜索。
折半查找的基本思想：减少一半的查找序列的长度，分而治之地进行关键字的查找。他的查找过程是：先确定待查找记录的所在的范围，然后逐渐缩小查找的范围，直至找到该记录为止（也可能查找失败）。
在最简单的形式中，二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符，并比较查找目标或将查找条件应用于集合的中间值；如果条件不满足或值不相等，则清除目标不可能存在的那一半，并在剩下的一半上继续查找，直到成功为止。如果查以空的一半结束，则无法满足条件，并且无法找到目标。

本题思路

1. 二分第k小的是多少
   二分解决判定性问题

我们二分出来第k小是x， 统计出有num个元素小于等于x
如果num≥k我们就可以减小上界
否则就可以提高下界

1. 对于二分出来的x，判断有多少个元素是小于等于x的
   我们可以先找元素大于x的，然后再用元素总个数减去大于x的元素个数

如何求有多少大于x的元素，我们可以再用一次二分查找upperbound函数，对n个数组都执行一次upperbound查找每个数组有多少比x大的

import java.util.Comparator;import java.util.PriorityQueue;
public class Solution {

    public long calc(int x, int[][] matrix) {
        long num = 0;
        for(int i = 0; i < matrix.length; i++) {
            int left = -1, right = matrix[i].length, pos = -1;
            //二分upper_bound查找多少个比x大的
            while(left + 1 < right) {
                int mid = left + (right - left) / 2;
                if(matrix[i][mid] > x) {
                    right = mid;
                    pos = mid;
                } else {
                    left = mid;
                }
            }
            if(pos == -1) {
                num += 0;
            } else {
                num += matrix[i].length - pos;
            }
        }
        return num;
    }
    /**
     * @param matrix: a matrix of integers
     * @param k: An integer
     * @return: the kth smallest number in the matrix
     */
    public int kthSmallest(int[][] matrix, int k) {
        // write your code here
        int left = matrix[0][0], right = matrix[0][0];

        //矩阵行数
        long n = matrix.length;
        //矩阵列数
        long m = matrix[0].length;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                //确定二分上下界
                left = Math.min(left, matrix[i][j]);
                right = Math.max(right, matrix[i][j]);
            }
        }
        left -= 1;
        right += 1;
        while(left + 1 < right) {
            //判定mid是不是第k小
            int mid = left + (right - left) / 2;
            long num = calc(mid, matrix);
            //如果比mid小的超过k个，就可以缩小上界，否则提高下界
            if(n * m - num >= (long)k) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}

更多题解参考：九章官网solution